모각코PS / 백준 1260 DFS와 BFS

모각코 PS스터디

지난주는 너무 바빠서 PS스터디 포스팅을 못 올렸네요. 백트래킹이었는데, 나중에라도 시간이 나면 올려보려고 합니다.

이번주 5주차 PS스터디 문제 주제는 그래프 탐색이었습니다. 세 문제 모두 DFS/BFS 문제였어요. 한 문제 씩 보면서 그래프 탐색에 대한 공부 방법, 주의점, 그리고 잡담 같은걸 좀 해볼게요.

그래프 탐색 문제는 흔히 '템플릿'이라고 하는 코딩스타일이 존재하죠. 조금만 구글링 해봐도 수두룩해요. 물론 제 블로그에도 있고요 ㅋㅋ. 그걸 보고 바로 원리를 이해할 수 있다면 좋겠지만 이해가 안된다면, 템플릿을 외워서라도 문제를 풀어보면서 익숙해지는 것도 좋은 방법 같습니다. 푸는데에 성공했다면 IDE로 옮겨서 디버깅을 실행해두고 한 스텝씩 따라가며 공부하는 거죠.
저는 그렇게 하진 않았는데...ㅋㅋ 그게 시간을 절약하기에는 좋은 방법 같더라구요!

문제와 풀이

---

문제 링크 : 백준 1260 - DFS와 BFS

👇펼쳐서 코드와 해설 읽기

들어온 값으로 인접행렬을 만들어서 탐색을 시도했습니다.
코드 자체는 템플릿에 가까운 형태라 따로 설명할 것이 없네요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Nick {

    static int n;
    static int m;
    static int v;
    static boolean[][] adjacencyMatrix;
    static boolean[] visited;
    static StringBuffer visitString;

    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());
        m = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());
        adjacencyMatrix = new boolean[n + 1][n + 1];

        String line = br.readLine();;
        while (line != null) {
            String[] l = line.split(" ");
            int i = Integer.parseInt(l[0]);
            int j = Integer.parseInt(l[1]);
            adjacencyMatrix[i][j] = true;
            adjacencyMatrix[j][i] = true;
            line = br.readLine();
        }
        br.close();

        /* dfs 호출 */
        visitString = new StringBuffer();
        visitString.append(v).append(" ");
        visited = new boolean[n + 1];
        visited[v] = true;
        dfs(v);
        System.out.println(visitString.toString());

        /* bfs 호출 */
        visitString = new StringBuffer();
        visitString.append(v).append(" ");
        visited = new boolean[n + 1];
        visited[v] = true;
        bfs(v);
        System.out.println(visitString.toString());
    }

    private static void bfs(int v) {
        Queue<Integer> bfsQueue = new LinkedList<>();
        bfsQueue.add(v);
        while (!bfsQueue.isEmpty()) {
            int nowVertex = bfsQueue.poll();
            for (int i = 0; i < adjacencyMatrix.length; i++) {
                if (adjacencyMatrix[nowVertex][i] && !visited[i]) {
                    visitString.append(i).append(" ");
                    visited[i] = true;
                    bfsQueue.add(i);
                }
            }
        }
    }

    private static void dfs(int v) {
        for (int i = 0; i < adjacencyMatrix.length; i++) {
            if (adjacencyMatrix[v][i] && !visited[i]) {
                visitString.append(i).append(" ");
                visited[i] = true;
                dfs(i);
            }
        }
    }

}

마무리

---

다 풀고 PR 날리기 전에, 저보다 먼저 올려주신 분이 두 분(o_b:us님, 소토님) 계셔서 코드를 참고해보았어요.

지금까지 BFS의 방문체크/출력값 추가 시점이 if (!visited[v]) 블록 안에서 이뤄져야한다고 당연히 여기고 있었는데, 그렇지 않더라구요.
어차피 순서에 맞게, 그리고 if (!visited[v])만 적절히 체크한다면, 실제 방문 시점에 append() / visited[v] = true;등의 처리를 해줘도 되는 것이었어요. 솔직히 아직 완전 이해되진 않았지만, 두 분의 코드를 보고 이해의 폭이 넓어진 것 같아서 정말 좋았습니다.

또, 소토님의 코드를 보니 DFS를 Stack 컬렉션으로 구현하셨더라구요. 그렇게 짜도 된다는 걸 알면서도 그렇게 짜본 적은 한 번도 없었는데(공부할 때 practice 정도를 짠 걸 제외하면), 소토님께서 Stack으로 접근하신 걸 보고 뭔가 한 대 맞은 것 같은 느낌이었어요. '실제로 짜보면서 이해하려고 노력하진 않았구나' 하는 생각이 들어서 반성하게 되었습니다.

간단한 문제라 리뷰할게 있을까? 하면서 가벼운 마음으로 열었는데, 정말 좋은 시간이었던 것 같습니다!