99클럽 코테 스터디 6일차 TIL (챌린저): [백준][Java] 2458 키 순서 - 골드4

 

문제 보기

https://www.acmicpc.net/problem/2458

 

 

풀이

 

미들러 문제가 이미 해결한 문제라 챌린저만 풀었다.

 

일단 그래프 탐색이 필요한 문제이다.

1. 자신으로부터 진행방향으로 탐색한 노드(자신보다 키가 큰 모든 사람들)

2. 자신으로부터 역방향으로 탐색한 노드(자신보다 키가 작은 모든 사람들)

1, 2번을 탐색해서 모든 노드 탐색이 가능하다면 자신의 키 순서를 정확하게 알 수 있다.

 

그림으로 보면 아래와 같다.

예시 그림에서 4번 노드를 기준으로 탐색해보자.

진행방향 탐색(주황)

역방향 탐색(빨강)

자신을 합하면 모든 노드를 탐색할 수 있다.

 

다른 노드들을 기준으로 탐색하면 어떻게 되는지 보자.

 

꼭 하나씩 탐색하지 못 하는 코드가 생긴다.

 

  private static void dfsBack(boolean[][] arr, int i, boolean[] visited, int[] counts, int cur) {
    for (int j = 1; j <= N; j++) {
      if (arr[i][j] && !visited[j]) {
        visited[j] = true;
        counts[cur]++;
        dfsBack(arr, j, visited, counts, cur);
      }
    }
  }

  private static void dfsFront(boolean[][] arr, int i, boolean[] visited, int[] counts, int cur) {
    for (int j = 1; j <= N; j++) {
      if (arr[j][i] && !visited[j]) {
        visited[j] = true;
        counts[cur]++;
        dfsFront(arr, j, visited, counts, cur);
      }
    }
  }

간단하게 뒤로 탐색하는 dfs, 앞으로 탐색하는 dfs 두 개를 만들었다.

counts 배열에 탐색한 노드의 수를 더해 N과 같으면 전체 count를 늘렸다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
  private static int N = 0;
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    String[] inputs = br.readLine().split(" ");
    N = Integer.parseInt(inputs[0]);
    int M = Integer.parseInt(inputs[1]);
    boolean[][] arr = new boolean[N + 1][N + 1];
    for (int i = 0; i < M; i++) {
      inputs = br.readLine().split(" ");
      arr[Integer.parseInt(inputs[0])][Integer.parseInt(inputs[1])] = true;
    }

    // b -> c 자신으로부터 앞으로
    // a -> b 자신으로부터 뒤로

    int[] counts = new int[N + 1];
    for (int i = 1; i <= N; i++) {
      boolean[] visited = new boolean[N + 1];
      visited[i] = true;
      counts[i] = 1;
      dfsBack(arr, i, visited, counts, i);
      dfsFront(arr, i, visited, counts, i);
    }

    int count = 0;
    for(int i = 1; i <= N; i++) {
      if(counts[i] == N) {
        count++;
      }
    }
    bw.write(count + "\n");

    bw.flush();
    bw.close();

  }

  private static void dfsBack(boolean[][] arr, int i, boolean[] visited, int[] counts, int cur) {
    for (int j = 1; j <= N; j++) {
      if (arr[i][j] && !visited[j]) {
        visited[j] = true;
        counts[cur]++;
        dfsBack(arr, j, visited, counts, cur);
      }
    }
  }

  private static void dfsFront(boolean[][] arr, int i, boolean[] visited, int[] counts, int cur) {
    for (int j = 1; j <= N; j++) {
      if (arr[j][i] && !visited[j]) {
        visited[j] = true;
        counts[cur]++;
        dfsFront(arr, j, visited, counts, cur);
      }
    }
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/2458.%E2%80%85%ED%82%A4%E2%80%85%EC%88%9C%EC%84%9C

CodingTest_AutoSave/백준/Gold/2458. 키 순서 at main · MetroDefro/CodingTest_AutoSave