99클럽 코테 스터디 8일차 TIL

백준 - 2644번

'앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.'

이 부분을 보고 부모 번호에서부터 시작되는 단방향 그래프로 생각했다.

그 생각에서 1시간을 넘게 벗어나지 못했다.

 

그리고 탐색은 무조건 1에서부터 시작해야한다는 고정관념이 있었다.

실제 촌수 계산할 때, 자신(나)부터 거슬러올라가면서 계산한다.

그래프 탐색 알고리즘 사용만을 생각하고, 문제와 상관없이 형식적으로 알고리즘을 사용했던 것 같다.

 

DFS 풀이

예제에서 촌수 계산을 해야하는 사람인 7번과 3번을 기준으로 계산해야 한다.

• 단방향이 아닌 양방향 그래프를 그린다.
• 7번부터 시작하여 3번까지 탐색한다.
• depth가 깊어질 때마다 count를 줘야 한다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    static ArrayList<Integer>[] relations; // 관계도
    static boolean[] visited; // 방문 여부
    static int result = -1;
    
    static void dfs(int current, int target, int depth) {
        visited[current] = true;

        if (current == target) {
            result = depth;
            return;
        }

        for (int next : relations[current]) {
            if (!visited[next]) {
                dfs(next, target, depth + 1);

                if (result != -1) return;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int start = sc.nextInt();
        int end = sc.nextInt();
        int m = sc.nextInt();

        relations = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            relations[i] = new ArrayList<>();
        }
        
        // 양방향 그래프
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            relations[x].add(y);
            relations[y].add(x);
        }

        dfs(start, end, 0);

        System.out.println(result);
        sc.close();
    }
}

DFS를 사용했지만 BFS도 사용할 수 있다.

그림에서는 트리 모양으로 그렸고, 간선도 직선 방향이다보니 DFS 밖에 생각나지 않았다.

 

BFS 풀이

7번을 기준으로, 다른 번호들은 7번과 몇 촌인지 기록하면서 탐색한다.

촌수 기록을 위한 distance 라는 배열 변수를 새로 선언했다.

static int bfs(int start, int end) {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited[start] = true;
    distance[start] = 0;

    while (!queue.isEmpty()) {
        int current = queue.remove();

        if (current == end) {
            return distance[current];
        }

        for (int next : relations[current]) {
            if (!visited[next]) {
                visited[next] = true;
                distance[next] = distance[current] + 1; // 각 번호마다 촌수 기록
                queue.add(next);
            }
        }
    }

    return -1;
}

아래의 표는 bfs 함수를 돌면서 각 번호가 7번과 몇 촌에 있는지 계산하는 것을 나타낸다.

내가 이해 안되서 작성했다.

촌수 계산	촌수	현재 queue 상태
distance[2] = distance[7] + 1	1촌	2
distance[1] = distance[2] + 1	2촌	1
distance[8] = distance[2] + 1	2촌	1 8
distance[9] = distance[2] + 1	2촌	1 8 9
distance[3] = distance[1] + 1	3촌	8 9 3

순차적으로 queue의 값을 꺼내고 종료값인 3이 오면 bfs 함수를 종료하고 결과를 출력한다.

---

지금까지 작성한 코드를 봤을 때, BFS 보다는 DFS 의 코드의 양도 적고 더 깔끔한 것 같다.

하지만 코드를 분석해보면 작은 범위이지만 재귀 함수가 호출될 때마다 내 머리의 복잡도가 높아졌다.

개인적으로 머리 복잡도가 높으면 값의 예측이 안될 때가 많았다.

BFS의 경우, 코드는 길지만 DFS와 반대로 깊어지는 사고에서 빠르게 나올 수 있었다.

 

백준 2644번 - 촌수계산

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