[Java]백준 1260 - DFS와 BFS

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

1260번: DFS와 BFS

주어진 정수를 입력받아 인접행렬 혹은 인접리스트를 만들고 DFS와 BFS로 탐색하는 문제이다.

DFS, BFS문제는 파이썬으로 많이 풀어봤지만 자바로는 한 번도 시도해보지 못했다. 언젠간 자바로도 그래프 문제를 풀어야 하니 생각난 김에 오늘 시작하게 되었다.

 

 

시나리오

정점의 수, 간선의 수, 시작점이 각각 첫번째 줄에 주어지고 나머지 줄은 두 정점이 이어진 정보를 표현한다.

1. 이를 입력받아서 2차원 int배열 adj를 만들어 인접행렬을 구현한다

2. DFS구현. 한 정점을 방문했을 때 현재 노드 정보 출력

3. BFS구현

4. DFS, BFS각각 호출

5. checkList만들어서 이미 다녀간 정점이라면 재방문하지 않도록 함.

 

 

 

내 코드

import java.util.*;
import java.io.*;
//방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문. 더 이상 방문할 수 없으면 종료

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    //4. DFS, BFS호출
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

        //n, m, v입력
        int[] nmv = new int[3];

        for (int i = 0; i < 3; i++) {
            String token = st.nextToken();
            nmv[i] = Integer.parseInt(token);
        }
        int n = nmv[0];
        int m = nmv[1];
        int v = nmv[2];

        int[][] adj = new int[n][n];

        makeAdj(nmv, adj);

        //5. CHECK LIST 만들어서 이미 다녀간 정점이면 재방문하지 않도록 함.
        boolean[] chk = makeChk(n, v);
        dfs(v - 1, adj, chk);
        System.out.println();
        chk = makeChk(n, v);
        bfs(v - 1, adj, chk);
    }

    //1. M개 줄을 입력받아 인접행렬(양방향) 만들기
    private static void makeAdj(int[] nmv, int[][] adj) throws IOException {
        int n = nmv[0];
        int m = nmv[1];

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v1 = 0;
            int v2 = 0;
            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());
            adj[v1 - 1][v2 - 1] = 1;
            adj[v2 - 1][v1 - 1] = 1;
        }
    }

    //2. DFS구현. 한 정점을 방문했을 때 현재 노드 정보 출력
    private static void dfs(int start, int[][] adj, boolean[] chk) {
        System.out.printf("%d ", start + 1);
        for (int i = 0; i < adj.length; i++) {
            if (adj[start][i] == 1) {
                //검증
                if (chk[i]) {
                    continue;
                }
                chk[i] = true;
                dfs(i, adj, chk);
            }
        }
    }

    //3. BFS구현
    private static void bfs(int start, int[][] adj, boolean[] chk) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        while (!q.isEmpty()) {
            int next = q.poll();
            System.out.printf("%d ", next + 1);
            for (int i = 0; i < adj.length; i++) {
                if (adj[next][i] == 1) {
                    if (chk[i]) {
                        continue;
                    }
                    q.offer(i);
                    chk[i] = true;
                }
            }
        }
        //최초 1회 start enq
        //while -> q가 빌 때까지
        //q.poll -> 출력 -> 해당 next 행 탐색
        // 1이면 enqueue 단, 방문이력없을 때
    }

    //5. CHECK LIST 만들어서 이미 다녀간 정점이면 재방문하지 않도록 함.
    private static boolean[] makeChk(int n, int v) {
        boolean[] chk = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (i == v - 1) {
                chk[i] = true;
                return chk;
            }
        }
        return null;
    }
}

코딩테스트를 준비하던 초반에는 문제를 읽자마자 곧바로 코드를 짜곤 했는데, 그것이 죄악이라는 것을 알고 최근에는 충분히 독해한 다음 손으로 끄적이고 문제를 풀려고 하고 있었다. 

그럼에도 실수를 크게 줄인다거나 하는 효과는 그다지 못느꼈던 것 같은데, 어제 멘토님이 알려주신 방법대로 10분에서 20분 정도 구현해야 할 내용을 주석과 함께 함수로 표현해 보기로 했다.

꼼꼼하게 pseudo code를 작성하니 순차적으로 코드를 짜게 되었고 100줄이 넘어가는 코드량에도 헤메지 않고 침착하게 잘 풀 수 있었다. 또한 놓치는 부분이 생겨 뒤늦게 구현하는 일도 없었다.

 

멘토님이 말씀하시길 시나리오를 정말 잘 작성하면 반례가 나올 일이 없다고 하셨고 20개 TC 중 13, 14개 정도 맞는거면 푸는 사람이 문제에서 놓치는 부분이 있었기 때문이라고 하셨다. 애초에 출제자가 각잡고 반례를 만들지는 않는다고..

 

아무쪼록 앞으로 문제 풀 때도 위 원칙을 적용해서 좋은 습관을 들여야겠다.