백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글

2644번 촌수 계산

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

2644번: 촌수계산

---

Comment

 DFS, BFS를  첫 입문할 때 하기 좋은 그래프 문제이다. 해당 문제는 DFS적으로 접근하면 Depth를 잘 활용할 수 있었는데, BFS를 활용해서 풀어볼 때 문제가 생겼었다. 직면했던 문제는 BFS에서는 Depth를 어떤 기준으로 체크할 수 있을까? 라는 고민을 많이 하게 한 문제였다.

---

hint

DFS, BFS 두가지 방법 모두 풀린다.

하지만 체감 난이도는 BFS가 더 어려웠던 것 같다.

---

Solution

• DFS

재귀호출할 때 매개변수를 통해서 해당 깊이를 더해가며 풀어보니 잘 해결되었다.

import java.io.*;
import java.util.*;
 
public class Main {
 
    static boolean[] check;
    static ArrayList<Integer>[] al;
    static int n, m, start, target;
    static boolean flag;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        target = Integer.parseInt(st.nextToken());
 
        m = Integer.parseInt(br.readLine());
 
        al = new ArrayList[n + 1];
        check = new boolean[n + 1];
 
        for (int i = 0; i < n + 1; i++) {
            al[i] = new ArrayList<>();
        }
 
        int x, y;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
 
            al[x].add(y);
            al[y].add(x);
        }
        check[start] = true;
        dfs(start, 0);
        if (!flag) {
            System.out.println(-1);
        }
 
    }
 
    static void dfs(int n, int count) { //7 3
        if (n == target) { //도착하면 flag 변경 후 종료
            flag = true;
            System.out.println(count);
            return;
        } else if (flag) { //이미 찾았으면 더이상 dfs를 돌 필요 없음
            return;
        } else {
            for (int a : al[n]) {
                if (!check[a]) {
                    check[a] = true;
                    dfs(a, count + 1);
                }
            }
        }
    }
}

• BFS

import java.io.*;
import java.util.*;
 
public class Main {
 
    static boolean[] check;
    static ArrayList<Integer>[] al;
    static int n, m, start, target;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        target = Integer.parseInt(st.nextToken());
 
        m = Integer.parseInt(br.readLine());
 
        al = new ArrayList[n + 1];
        check = new boolean[n + 1];
 
        for (int i = 0; i < n + 1; i++) {
            al[i] = new ArrayList<>();
        }
 
        int x, y;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
 
            al[x].add(y);
            al[y].add(x);
        }
 
        bfs(start, target);
 
    }
 
    static void bfs(int start, int target) { // null을 활용해서 깊이 구분자를 생성
        int count = 0;
 
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        q.add(null);
        check[start] = true;
 
        while (!q.isEmpty()) {
            Integer now = q.poll();//null을 활용하기 위해 Integer로 
 
            if(now == null) {//null을 만날 때마다 깊이가 깊어짐 count++
                if(!q.isEmpty()) {
                    q.add(null);
                    count++;
                }
            }else {
                for (int y : al[now]) {
                    if (!check[y]) {
                        check[y] = true;
                        if (y == target) { // bfs깊이에 따라서 체크 후 해당 깊이 출력
                            System.out.println(count + 1);
                            return;
                        }
                        q.add(y);
                    }
                }
            }
        }
        System.out.println(-1);
    }
}

내가 만질 때는 null을 Queue에 넣어서 구분자로 생각하고 null을 만날 때마다 count가 1씩 증가하도록 구현했었는데, 좀 더 직관적인 방법이 좋았을거라 생각했고, 스터디를 진행하는 다른 사람이 푼 것을 봤을 때 distance라는 배열을 만들어서 해당 값을 누적되게 구현했는데 더 좋은 방법 같았다.

어쨌든 그래프에서 DFS, BFS를 둘 다 사용해보기에 좋은 문제였던 것 같다!