[알고리즘 PS] 백준 1260번 DFS와 BFS 자바 문제풀이

문제

해당 포스팅은 백준의 1260번 DFS와 BFS 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

해결법

해당 문제를 해결하기 위해서 우선 그래프를 구현해야 한다.

그래프를 구현하는 방법에는 크게 2가지가 있다.

이 2가지 (인접 행렬, 인접 리스트)로 우선 그래프를 구현 한 뒤 탐색을 수행하면 될 것 같다.

만약 구현 방법에 대해서 알지 못한다면 아래 링크를 통해서 한 번 확인하는 것도 좋은 선택이다.

• 인접 리스트 구현 방법
• 인접 행렬 구현 방법

그래프의 DFS와 BFS를 구현하는 방법에는 여러 방법이 있다.

1. 스택으로 DFS 구현하기
2. 재귀 호출로 DFS 구현하기
3. 큐로 BFS 구현하기

위의 3가지 방법을 모두 경험해보며 실행시간을 비교해보자.

접근법

우선 우리는 인접 리스트와 방문 체크 배열의 길이를 입력 받은 길이 + 1로 쓸 것이다.
여기서 2가지 옵션이 존재한다.

1. 인접 리스트와 방문 체크 배열의 길이를 입력 받은 길이 그대로 쓸 것인가.
2. 인접 리스트와 방문 체크 배열의 길이를 입력 받은 길이 + 1로 쓸 것인가.

1번의 경우 출력과 그래프 작업에 + 1과 -1을 해줘야 한다.

 

하지만 2번의 경우 1번에 비해 메모리는 더 쓰겠지만 그래도 우리가 코딩하기 편하다.

 

이제 실질적으로 DFS와 BFS를 구현해보자.

스택으로 DFS 구현하기

private static void dfsByStack(int x) {
  Stack<Integer> stack = new Stack<>();
  boolean flag;
  visited[x] = true;
  sb.append(x).append(" ");
  stack.push(x);
  while(!stack.isEmpty()) {
      x = stack.peek();
      int size = graph.get(x).size();
      flag = false;
      for (int i = 0; i < size; i++) {
          int value = graph.get(x).get(i);
          if (!visited[value]) {
              stack.push(value);
              sb.append(value).append(" ");
              visited[value] = true;
              flag = true;
              break;
          }
      }
      if(!flag) {
          stack.pop();
      }
  }
}

재귀호출로 DFS 구현하기

private static void dfsByRecursive(int x) {
  if(visited[x]) return; // 방문한 적이 있는 노드면 바로 나가
  visited[x] = true;
  sb.append(x).append(" ");
  for(int value : graph.get(x)) {
    if(!visited[value]) dfsByRecursive(value);
  }
}

큐로 BFS 구현하기

private static void bfs(int start) {
  Queue<Integer> queue = new LinkedList<>();
  visited[start] = true;
  queue.add(start);

while(!queue.isEmpty()) {
    int x = queue.remove();
    sb.append(x).append(" ");
    for (int i = 0; i < graph.get(x).size(); i++) {
        int value = graph.get(x).get(i);
        if(!visited[value]) {
            visited[value] = true;
            queue.add(value);
        }
    }
  }
}

오답 후보

문제에서 정점 번호가 작은 것을 먼저 방문하라고 했다.

정점 번호가 작은 것 부터 방문 하려면 우리의 인접 리스트에 존재하는 각각의 리스트들이 오름차순으로 정렬되어 있어야 한다.

 

그래서 그래프 구현이 끝나고 실질적인 탐색에 들어가기 전에 정렬을 해주도록 하면 된다.

정답 코드

public class Main {

    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] nmv = br.readLine().split(" ");

        int n = Integer.parseInt(nmv[0]);
        int m = Integer.parseInt(nmv[1]);
        int v = Integer.parseInt(nmv[2]);

        // 방문 체크 배열 생성

        // 인접 리스트 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 입력 처리 (그래프 연결)
        for(int i = 0; i < m; i++) {
            String[] n1n2 = br.readLine().split(" ");
            int n1 = Integer.parseInt(n1n2[0]);
            int n2 = Integer.parseInt(n1n2[1]);

            graph.get(n1).add(n2);
            graph.get(n2).add(n1);
        }
        for (int i = 0; i <= n; i++) {
            Collections.sort(graph.get(i));
        }

        visited = new boolean[n + 1];
        dfsByRecursive(v);
        bw.flush();
        sb.append("\n");
        visited = new boolean[n + 1];
        bfs(v);
        System.out.println(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void dfsByStack(int x) {
        Stack<Integer> stack = new Stack<>();
        boolean flag;
        visited[x] = true;
        sb.append(x).append(" ");
        stack.push(x);
        while(!stack.isEmpty()) {
            x = stack.peek();
            int size = graph.get(x).size();
            flag = false;
            for (int i = 0; i < size; i++) {
                int value = graph.get(x).get(i);
                if (!visited[value]) {
                    stack.push(value);
                    sb.append(value).append(" ");
                    visited[value] = true;
                    flag = true;
                    break;
                }
            }
            if(!flag) {
                stack.pop();
            }
        }
    }

    private static void dfsByRecursive(int x) {
        visited[x] = true;

        sb.append(x).append(" ");

        int size = graph.get(x).size();

        for (int i = 0; i < size; i++) {
            int value = graph.get(x).get(i);
            if(!visited[value]) {
                dfsByRecursive(value);
            }
        }
    }

    private static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.add(start);

        while(!queue.isEmpty()) {
            int x = queue.remove();
            sb.append(x).append(" ");
            for (int i = 0; i < graph.get(x).size(); i++) {
                int value = graph.get(x).get(i);
                if(!visited[value]) {
                    visited[value] = true;
                    queue.add(value);
                }
            }
        }
    }
}

 

---

문제 회고

이번 문제에서는 출력에서 애를 많이 먹었다.
메서드에서 sb로 append를 해주는 로직에서 나는 한 번의 탐색이 끝날 때 bw로 출력하려 했다.
그래서 만약 답이 4개라면 8개가 출력되곤 했다.
문제의 로직을 짜는 것도 중요하나 출력 관리도 중요하단 것을 또 알게 되었다.

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.