[실버 2] 촌수계산

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

2644번: 촌수계산

풀기 전:

뭐야 이거 몇 번 거쳐야 가지는지 구하는 거네

dfs bfs 어떤 거든지 상관없겠다

 

dfs로 오랜만에 풀어보자

import java.io.*;
import java.util.*;

class Main {
    static int answer=-1;

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

        int n;
        int person1, person2;
        int m;
        int x, y;
        int[][] graph;

        n = Integer.parseInt(br.readLine());
        graph = new int[n + 1][n + 1];

        st = new StringTokenizer(br.readLine());
        person1 = Integer.parseInt(st.nextToken());
        person2 = Integer.parseInt(st.nextToken());

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

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

무난하게 입력받고

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

        dfs(graph,visited,person1,person2,0);
        sb.append(answer);
        System.out.println(sb);

    }
    public static void dfs(int[][] graph, boolean[] visited ,int start, int end ,int count){

        if(start == end)
            answer = count;

        visited[start]=true;

        for( int i = 1 ; i< graph.length; i++){
            if(!visited[i]&& graph[start][i] ==1)
                dfs(graph,visited,i,end,count+1);
        }
    }
}

무난하게 dfs