[백준] Silver II. 촌수 계산

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

 

사용 알고리즘

• 그래프 탐색
• DFS

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static int n, a, b, m;
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean [] visited;
    static int res = -1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(br.readLine());

        for(int i = 0; i <= n; i++) { // 초기화
            graph.add(new ArrayList<>());
        }
        visited = new boolean[n + 1];

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        dfs(a, b, 0);
        System.out.println(res);
    }

    public static void dfs(int start, int end, int depth) {
        visited[start] = true;
        if (start == end) {
            res = depth;
            return;
        }

        for(int next : graph.get(start)) {
            if (!visited[next]) {
                dfs(next, end, depth + 1);
            }
        }
    }

}

 

회고

 

주어진 예제에서

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

 

7과 3까지의 거리(depth)를 구하면 되는 문제였다. DFS로 풀 수 있을것 같아서 풀이를 진행했다.

 

dfs 탐색 조건은 7이 3에 도달할 때, dfs(start, end, depth)로 돌려서 start가 end에 도달할 때, depth를 반환해주고 만약에 도달할 수 없다면, 이어져 있지 않다는 뜻이므로 -1을 리턴해주었다.

 

매번 dfs를 탐색할 때마다 

dfs(next, end, depth + 1);

 

시작하는 노드를 다음 노드로 업데이트 해주어 모든 노드에 대해서 탐색이 가능하도록 했고, depth를 1만큼 늘려줘서 거리를 계산하도록 구현하였다.