[JAVA] 촌수 계산 (백준 2644)

 

dfs,bfs 문제가 제일 재밌는거 같다. 

 

출발지와 목적지를 정하고 가는 데 몇군데를 거치느냐를 따지면 된다.

 

예를 들어, 7번 목적지에서 3번으로 갈려면?

 

최소 3번만에 갈 수있다.

 

 

dfs로 위의 로직을 구현한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    static int n;
    static int st,ed;
    static int answer=-1;

    public static void main(String[] args) throws IOException{
        FastScanner fs = new FastScanner();
        n = fs.nextInt();
        Node[] nodes = new Node[n];
        for(int i=0;i<n;i++) nodes[i] = new Node();

        st = fs.nextInt()-1;
        ed = fs.nextInt()-1;

        // destination
        nodes[ed].isDest = 1;

        //makeConnect - ok
        makeConnect(fs,nodes);

        nodes[st].visited=1;
        dfs(nodes[st],0);



        System.out.printf("%d\n",answer);

    }
    private static void dfs(Node node,int sum){
        if(node.isDest==1){
            answer = sum;
            return;
        }else {
            for (Node nd : node.con) {
                if(nd.visited==0){
                    nd.visited=1;
                    dfs(nd,sum+1);
                    nd.visited=0;
                }
            }
        }
    }

    private static void makeConnect(FastScanner fs,Node[] nodes) throws IOException {
        int lineNum = fs.nextInt();
        for(int i=0;i<lineNum;i++){
            int a = fs.nextInt()-1;
            int b = fs.nextInt()-1;
            nodes[a].con.add(nodes[b]);
            nodes[b].con.add(nodes[a]);
        }
    }

    static class Node{
        int visited = 0;
        int isDest = 0;
        List<Node> con = new ArrayList<>();

        public String toString(){
            return ""+con.size();
        }
    }


    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public String next() throws IOException {
            while(!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException{
            return Integer.parseInt(next());
        }
    }
}