[99클럽 코테 스터디] 6일차 TIL - 백준 1260번 DFS와 BFS

 

오늘의 문제는 백준 1260번 'DFS와 BFS'였다.

 

이 문제는 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;

// 1260 DFS와 BFS
public class Main {
    static int[][] graph;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();
    static Queue<Integer> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        graph = new int[N + 1][N + 1];
        visited = new boolean[N + 1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a][b] = graph[b][a] = 1;
        }

        Dfs(V);
        sb.append("\n");
        visited = new boolean[N + 1];
        Bfs(V);

        System.out.println(sb.toString());
    }

    static void Dfs(int v) {
        visited[v] = true;
        // 재귀 사용
        sb.append(v).append(" ");
        for (int i = 0; i < graph.length; i++) {
            if (graph[v][i] == 1 && !visited[i])
                Dfs(i);
        }
    }

    static void Bfs(int v) {
        q.add(v);
        visited[v] = true;
        // 큐 사용
        while (!q.isEmpty()) {
            v = q.poll();
            sb.append(v).append(" ");

            for (int i = 0; i < graph.length; i++) {
                if (graph[v][i] == 1 && !visited[i]) {
                    q.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

 

문제 풀이에 앞서, 먼저 개념에 대해 살펴보겠다.

 

DFS (Depth - First Search)

DFS는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

동작 과정

재귀 함수와 스택을 사용하는데, 재귀를 사용할 수 없을 때 스택을 사용한다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 인접한 노드 중 방문하지 않은 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다.
   • 인접 노드가 모두 방문 처리가 되었다면 스택에서 최상단 노드를 꺼낸다.
   • 즉, 매번 최상단 원소를 기준으로 방문하지 않은 인접 노드가 있으면 그 노드로 방문을 수행 (재귀 O)
3. 위 과정을 할 수 없을 때까지 반복한다.

 

DFS를 사용하는 문제 유형

• 특정 경로를 찾는 문제
• 모든 노드를 방문해야 하는 문제

이러한 알고리즘이기 때문에, 위 코드에서 DFS에 대해

최상단 원소를 기준으로 재귀를 활용하여 구현했다.

 

 

BFS (Breadth-Fist Search)

BFS는 너비 우선 탐색이라고 부르며, 그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.

 

동작 과정

BFS는 큐 자료구조를 사용한다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드이면서 방문 처리되지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
   • DFS와 달리 BFS는 해당 시점에서 인접한 노드를 한 번에 전부 큐에 넣는다.
   • 해당 시점에 큐의 첫 번째 요소가 기준이 된다.
3.  위 과정을 할 수 없을 때까지 반복한다.

 

BFS를 사용하는 문제 유형

• 최단 경로를 구하는 경우
• 모든 간선의 가중치가 없거나 1일 경우
  • 모든 간선의 가중치가 다를 경우 최단 경로를 구할 수 X

 

 

오늘의 회고

• DFS와 BFS의 개념을 다시 복기하느라 시간이 많이 지체된 것이 아쉽다.
• BFS를 구현할 때 큐를 사용하는 것이 익숙하지 않아서 인터넷에 검색을 해서 해결했다.
• DFS 함수를 불러온 뒤 BFS 함수를 불러오기 전에 visited를 초기화해주지 않아서 원하는 답이 나오지 않았었다.
  • 실수 빈도가 많은 부분이 초기화 부분이다! 빠짐없이 확인하도록 해야겠다.