백준 촌수 계산

오랜만에 BFS푸니까 이틀정도 걸림

 

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

 

package a03;
import java.util.*;

public class Test0321 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int people_n = sc.nextInt();//3
        int people_a = sc.nextInt();//1
        int people_b = sc.nextInt();//2
        int relation = sc.nextInt();

        int visited[] = new int[people_n + 1];
        List<Integer>[] graph = new ArrayList[people_n + 1];

        for (int i = 1; i <= people_n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 1; i <= relation; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph[x].add(y);
            graph[y].add(x);
        }
        System.out.println(search(graph, visited, people_a, people_b, 0));
    }

    public static int search(List<Integer>[] graph, int visited[], int current, int target, int depth) {
        visited[current]=1;

        if (current == target) {
            return depth;
        }
        for(int i=0; i<graph[current].size(); i++){
            int next = graph[current].get(i);
            if(visited[next]==0){
                int result = search(graph,visited,next,target,depth+1);
                if(result !=-1){
                    return result;
                }
            }
        }
        return -1;
    }
}

 

설명하자면

 

값을 입력받고 -> 양방향 그래프 초기화 -> DFS로 재귀 호출 -> 방문 한적이 없는 값이면 다음 진행, 현재 값이 target값과 같다면 종료

 

사실 엄청 간단한 BFS문제인데 막상 오랜만에 풀려고 하면 생각을 좀 해야한다.