99클럽 코테 스터디 8일차 TIL DFS(촌수계산)

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

 

오늘은 작년에 풀었던 문제였다

전형적인 DFS 문제로 시작노드에서부터 목표노드 까지의 거리를 구하면 된다!

방문 순서가 아닌 노드 사이의 거리이므로 dfs 함수에 재귀로 같이 cnt를 돌려야 한다.

** 도착하지 못하는 경우 -1 출력이므로, ans는 -1로 초기화 해주기!!

 

<제출코드>

package STUDY;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Day08_BOJ_2644 {

    static int n, m;
    static int s, e;
    static int ans = -1;
    static boolean[] visited;
    static List<Integer>[] list;

    public static void dfs(int x, int target, int cnt){
        visited[x] = true;
        if(x == target){
            ans = cnt;
            return;
        }
        for(int i=0; i<list[x].size(); i++){
            int now = list[x].get(i);
            if(visited[now]) continue;
            dfs(now, target, cnt+1);
        }
    }

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

        n = Integer.parseInt(st.nextToken());
        list = new ArrayList[n+1];
        for(int i=0; i<n+1; i++){
            list[i] = new ArrayList<>();
        }
        st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken());       // 촌수계산 시작번호
        e = Integer.parseInt(st.nextToken());       // 촌수계산 끝번호
        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
            list[y].add(x);
        }
        visited = new boolean[n+1];
        dfs(s, e, 0);
        System.out.println(ans);
    }
}