[TIL] 99클럽 코테 스터디 8일차 TIL + 백준 2644 촌수계산

 

문제 풀이

 

문제 탐색하기

DFS 알고리즘을 활용하여 풀이 설계하기

깊이 우선 탐색 알고리즘에 대해서는 아래의 게시글에 개념을 설명해두었습니다.

https://coding-babo.tistory.com/151

[TIL] 99클럽 코테 스터디 4일차 TIL + 백준 24479 깊이 우선 탐색 1

 

촌수를 계산하기 위해서 DFS 알고리즘을 활용하였습니다. 사람을 노드라고 생각하면 방문하는 노드를 배열에 체크하면서 원하는 사람이 나올때까지 탐색을 반복합니다. 재귀호출을 통해서 탐색을 할때 방문하는 노드의 카운트를 함께 매개변수로 가지고 있게되면 문제에서 주어지는 두 사람의 촌수를 구할 수 있습니다.

 

문제 풀이

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

public class Main {

    static boolean[] visited;
    static int count = -1;
    static boolean chk;
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        visited = new boolean[n+1];

        for(int i=0; i<=n; i++){
            list.add(new ArrayList<>());
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int m = Integer.parseInt(br.readLine());
        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.get(x).add(y);
            list.get(y).add(x);
        }

        for(int i=1; i<=m; i++){
            Collections.sort(list.get(i));
        }

        dfs(Math.min(a, b), Math.max(a, b), 0);
        System.out.println(count);
    }

    private static void dfs(int x, int y, int cnt){
        visited[x] = true;

        for(int i=0; i<list.get(x).size(); i++){
            if(!visited[list.get(x).get(i)]){
                if(list.get(x).get(i) == y){
                    count = cnt+1;
                    return;
                }

                dfs(list.get(x).get(i), y, cnt+1);
            }
        }
    }
}

 

 

오늘의 회고

처음에는 방문한 노드의 배열이 false일때마다 촌수를 계산하기 위한 카운트 변수를 +1 했습니다. 이렇게 해서 풀었더니 백트래킹 하는 경우에도 계속 카운트가 올라가는 문제로 인하여 정답을 도출해낼 수 없었습니다.. 결국 열심히 서칭을 한 결과,, 카운트 값을 dfs 함수가 호출될 때마다 지니고 있으면 해당 노드를 방문했을 때의 카운트 값을 구할 수 있다는 것을 알 수 있었습니다! 

증말 어렵네요....