[BOJ - JAVA] 2644 - 촌수계산 (DFS)

# 주소

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

2644번: 촌수계산

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.*;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    static int node;
    static int n,m,k;
    static int[][] arr;
    static boolean[]visit;
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        node = scan.nextInt();
        n = scan.nextInt();
        m = scan.nextInt();
        k = scan.nextInt();
        arr = new int[node+1][node+1];
        for(int i = 1; i <= k; i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            arr[a][b] = arr[b][a] = 1;
        }
        visit = new boolean[node+1];
        dfs(n,m,0);
        System.out.println(-1);
    }
    public static void dfs(int x, int y, int cnt) {
        visit[x] = true;
        LinkedList<Point> queue = new LinkedList<>();
        queue.offer(new Point(x,y));
        while(!queue.isEmpty()){
            Point now = queue.poll();
            if(now.x == m){
                System.out.println(cnt);
                System.exit(0);
            }
            for(int i = 1; i <= node; i++){
                if(arr[now.x][i] == 1 && visit[i] == false){
                    dfs(i,now.x,cnt+1);
                }
            }
        }
    }
}

정석의 DFS 문제였습니다.

출력문에서 자꾸 0이 나와서 고민을 조금 많이 한 것 같습니다.

차근차근 짚어가보겠습니다.

static으로 선언한 dx, dy는 신경안쓰셔도 됩니다. 

상하좌우로 이동하여 인덱스를 찾아가는 문제가 아니기 때문입니다.

이 문제에서는 노드의 연결이 주어져있고 그 노드의 관계를 arr에 1로 담는 것이 핵심입니다.

지금 문제에서 나온 예제대로 arr배열을 만들면

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

	1	2	3	4	5	6	7	8	9
1		1	1
2	1						1	1	1
3	1
4					1	1
5				1
6				1
7		1
8		1
9		1

이런 그림이 그려집니다.

여기에서, Queue를 이용하여 LinkedList 자료구조에 문제에서 물어보는 점(7,3)을 삽입합니다.

(7,3이 몇촌 관계인지 묻는 문제입니다.)

그리고 while문을 써주시고 방금 삽입한 점을 now로 끌고와서 이 now의 x점이 문제에서의 y값이 되면 연산 횟수를 출력합니다.

자 왜 now.x 가 m이 되어야 정답이 될까요???

그걸 알기 전 먼저 이 문제의 원리를 이해할 필요가 있습니다.

while(!queue.isEmpty()){
            Point now = queue.poll();
            if(now.x == m){
                System.out.println(cnt);
                System.exit(0);
            }
            for(int i = 1; i <= node; i++){
                if(arr[now.x][i] == 1 && visit[i] == false){
                    dfs(i,now.x,cnt+1);
                }
            }
        }

이 문제의 가장 핵심 코드는 이곳에 담겨있습니다.

밑의 for문을 보시면 i의 모든 node에 대해, arr의 현재 [now.x좌표(최초엔 7)][i (i는 1부터 9까지]값이 1이 되면

<-> arr[7][i] == 1이 되게하는 i값. 얼마죠???

2이죠??? 이 2를 찾으면 dfs에 다시 넘깁니다. (visit[i] == false는 꼭 달아주셔야 재방문 안합니다. 촌수 계산하는데 중복해서 간선을 밟을 필요는 없으니까요)

그리고 이 dfs문을 실행할 때마다 cnt+1을 꼭 해주시고 dfs에 now.x와 i의 순서를 바꾸어서 dfs(i,now.x, cnt+1)을 실행합니다.

자, 궁금하시죠? 이게 왜 바뀌어서 실행을 해야할까요?

생각해봅시다. 제일 처음 7,3을 우리는 제일 먼저 queue에 넣었습니다.

이 7,3에서 우린 가장 가까운 친인척을 찾기 위해 7과 연결되어 있는 노드를 찾아볼 것입니다.

그런데 7과 연결된 점 중 제일 먼저 눈에 띄는건 2가 되겠습니다.

그럼 이 2를 입력 받고 저희는 다시 arr[2][i]에 대해 실행해보고자 합니다.

(7,3에서 했던 것처럼 이번엔 2,i 중 i가 뭐가 될지 또다시 for문 탐색)

이를 통해 새롭게 i가 구해질거고 이 i는 1이 찾아집니다.

그리고 다시 dfs에 1을 넣고 또 돌립니다.

돌리면 arr[1][i] == 1이 되는 i값은 3이지요?

이 3에 우리가 도달을 했네요??

그럼 이 3을 마지막으로 dfs에 넣고 돌리되 if문을 통해 now.x(3) == m(3)이면 출력을 해주어야 비로소 정답이 출력되는 것입니다.

그래서 now.x 가 m일 때 출력하란 얘기가 이 말입니다.

그리고 여기서 System.exit(0)을 입력하시면 시스템이 종료됩니다.

그러나, dfs문이 완전히 다 실행되고 끝나게 되었을 때 dfs(n,m,0) 밑에 System.out,println(-1)을 입력하시면 dfs문이 끝나고도(시스템이 종료 안된 상태에서도) main함수는 동작중이므로 -1을 출력하게 됩니다.

즉, -1을 출력할 때는 적합한 now.x == m이 되는 경우가 없다는 얘기이므로 이는 친인척관계가 아니라는 얘기가 되겠습니다.

감사합니다.