[백준] 2644번 - 촌수계산 (Java)

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

2644번: 촌수계산

 

<문제 분석>

1. 부모-자식 관계지만 거슬러 올라갈 수 있으므로 방향이 없는 트리와 같다.

2. DFS 파라미터로   정점 번호와 count를 넘겨준다.

3. Y를 찾지 못하면 flag를 둬서 -1을 출력한다.

 

<코드 구현 - 1차>

import java.util.*;

/*
[백준] 2644번 - 촌수계산 (Java)
*/

public class Main {
    static int N, M, X, Y;
    ArrayList<Integer> A[];    
    static boolean visited[];

    void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        X = in.nextInt();
        Y = in.nextInt();
        M = in.nextInt();
        A = new ArrayList[N+1];
        for (int i=1; i<=N; i++) {
            A[i] = new ArrayList<Integer>();
        }
        
        for (int i=1; i<=M; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            A[x].add(y);
            A[y].add(x);
        }
    }

    void DFS(int v, int count) {
        visited[v] = true;
        max = Math.max(max, count);
        if (v == Y) {
            found = true;
            return;
        }
        for (int x : A[v]) {
            if (visited[x]) continue;
            DFS(x, count+1);
        }
    }

    int max = 0;
    boolean found;
    void Solve() {
        visited = new boolean[N+1];
        DFS(X, 0);
        if (found)
            System.out.println(max);
        else 
            System.out.println(-1);
    }
    
	public static void main(String[] args) {
		Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

<제출결과>

24%에서 실패함.

 

<코드 구현 - 2차>

import java.util.*;

/*
[백준] 2644번 - 촌수계산 (Java)
*/

public class Main {
    static int N, M, X, Y;
    ArrayList<Integer> A[];    
    static boolean visited[];

    void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        X = in.nextInt();
        Y = in.nextInt();
        M = in.nextInt();
        A = new ArrayList[N+1];
        for (int i=1; i<=N; i++) {
            A[i] = new ArrayList<>();
        }
        
        for (int i=1; i<=M; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            A[x].add(y);
            A[y].add(x);
        }
    }

    void DFS(int start, int end, int count) {
        if (start == end) {
            ans = count;
            return;
        }
        visited[start] = true;
        for (int next : A[start]) {
            if (visited[next]) continue;
            DFS(next, end, count+1);
        }
    }

    int ans = -1;
    void Solve() {
        visited = new boolean[N+1];
        DFS(X, Y, 0);
        System.out.println(ans);
    }
    
	public static void main(String[] args) {
		Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

<제출결과>

<수정점>

1. dfs 파라미터를 start, end 두개 모두 가지고 다니도록 변경함.

2. count 값의 저장은 start == end 일 때만 하도록 변경함.

3. found flag 변수 삭제함.