[PS] 99클럽 코테 스터디 17일차 TIL (촌수계산)

문제

문제 링크

설명

가계도에서 두 사람간의 촌수를 계산하는 문제. 첫번째 예제로 주어진 촌수에 대해 2차원 배열로 표시하면 아래와 같은 그림이 된다.

풀이 (DFS)

관계를 양방향으로 표시하고 방문한 노드에 대해서는 visited 배열의 값을 true 로 바꿔준다. 한번 호출될때 마다 depth 를 증가시킨다. 이 값이 여기선 촌수가 된다. 7번 사람과 3번 사람의 촌수를 구하려면 7 -> 2 -> 1 -> 3 순으로 탐색하면 된다. 3번 사람까지 탐색이 완료되면 depth 를 리턴한다.

public class Main {

  static boolean[][] graph;
  static boolean[] visited;
  static int answer = -1;
  static int n, m;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    n = Integer.parseInt(br.readLine());

    graph = new boolean[n + 1][n + 1];
    visited = new boolean[n + 1];

    StringTokenizer st = new StringTokenizer(br.readLine());
    int p1 = Integer.parseInt(st.nextToken());
    int p2 = Integer.parseInt(st.nextToken());

    m = Integer.parseInt(br.readLine());
    int x, y;
    for (int i = 0; i < m; i++) {
      StringTokenizer kinship = new StringTokenizer(br.readLine());
      x = Integer.parseInt(kinship.nextToken());
      y = Integer.parseInt(kinship.nextToken());
      // 서로 관계를 맺어준다
      graph[x][y] = true;
      graph[y][x] = true;
    }

    dfs(p1, p2, 0);
    System.out.println(answer);
  }

  private static void dfs(int p1, int p2, int depth) {
    if (p1 == p2) {
      answer = depth;
      return;
    }
    visited[p1] = true;

    for (int j = 1; j <= n; j++) {
      if (!visited[j] && graph[p1][j]) { // 방문한 적이 없고, 해당 노드의 graph 가 true 이면 (친척관계이면) 방문
        dfs(j, p2, depth + 1);
      }
    }
  }
}

풀이 (BFS)

dfs 가 최초 시작지점 부터 이어진 노드를 끝까지 재귀적으로 탐색하면서 찾는 방식이라면, bfs 는 시작 노드의 자식 노드들을 모두 Queue 에 담았다가 순차적으로 방문하면서 찾는 방식이다. bfs 호출 시 시작노드와 함께 depth 를 전달한다.

public class Main {

  static boolean[][] graph;
  static boolean[] visited;
  static int answer = -1;
  static int n, m;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    n = Integer.parseInt(br.readLine());

    graph = new boolean[n + 1][n + 1];
    visited = new boolean[n + 1];

    StringTokenizer st = new StringTokenizer(br.readLine());
    int p1 = Integer.parseInt(st.nextToken());
    int p2 = Integer.parseInt(st.nextToken());

    m = Integer.parseInt(br.readLine());
    int x, y;
    for (int i = 0; i < m; i++) {
      StringTokenizer kinship = new StringTokenizer(br.readLine());
      x = Integer.parseInt(kinship.nextToken());
      y = Integer.parseInt(kinship.nextToken());
      graph[x][y] = true;
      graph[y][x] = true;
    }

    System.out.println(bfs(p1, p2));
  }

  private static int bfs(int p1, int p2) {
    LinkedList<int[]> queue = new LinkedList<>();
    queue.add(new int[] {p1, 0});
    visited[p1] = true;

    while (!queue.isEmpty()) {
      int[] current = queue.poll();
      int node = current[0];
      int depth = current[1];

      if (node == p2) {
        return depth;
      }

      for (int i = 1; i <= n; i++) {
        if (!visited[i] && graph[node][i]) {
          visited[i] = true;
          queue.add(new int[] {i, depth + 1});
        }
      }
    }
    return answer;
  }
}