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

문제 설명

 

❝문제❞

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

❝입력❞

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

❝출력❞

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

❝테스트 예제❞

풀이 코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int node,line,start;
    static int[][] lines;
    static boolean[] visited;
    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());

        //첫 줄 입력 받기(정점, 간선, 시작정점)
        node = Integer.parseInt(st.nextToken());
        line = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(st.nextToken());

        //정점간의 관계를 저장할 배열
        lines = new int[node+1][node+1];
        //방문한 정점 기록용 배열
        visited = new boolean[node+1];

        //간선 입력 받기
        for(int i = 0; i<line; i++){
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            lines[a][b] = lines[b][a] = 1;
        }

        //dfs 구하기
        dfs(start);
        //출력값 개행 문자 추가 및 visited 배열 초기화
        sb.append("\n");
        Arrays.fill(visited, false);
        //bfs 구하기
        bfs(start);
        //출력
        System.out.println(sb);
    }
    public static void dfs(int start){
        //방문한 노드 기록하기
        visited[start] = true;
        //출력 stringbuilder에 append
        sb.append(start + " ");

        for(int i = 1; i<= node; i++) {
            if (lines[start][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }
    public static void bfs(int start){
        q.add(start);
        visited[start] = true;

        while(!q.isEmpty()){
        	//탐색 시작 노드 변경
            start = q.poll();
            sb.append(start+ " ");
            for(int i = 1; i<= node; i++){
                if(lines[start][i] == 1 && !visited[i]){
                    q.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

 

 

문제 이해하기

✔️ DFS (깊이 우선 탐색)

 연결된 정점들 중 가장 작은 노드 부터 방문, 이동후 그 노드에서 또 이동 / 즉, 꼬리에 꼬리를 무는 알고리즘이라고 생각하면 편합니다. 

예제 1번의 예시로 시작 정점이 1인 경우,

1 -> 2 (문제에서 작은 정점부터 방문한다고 조건이 주어짐.) 

2 -> 4

4 -> 3 

따라서 1 -> 2 -> 4 -> 3 는 dfs 탐색의 결과입니다. 

 

✔️ BFS (너비 우선 탐색)

 연결된 정점들 중 가장 작은 노드 부터 방문, 다시 돌아와서 그 다음으로 작은 노드 방문 / 즉, 시작 정점에서 갈 수 있는 정점들은 모두 방문 후 시작 정점을 다음 정점으로 변경 후 반복.

예제 1번의 예시로 시작 정점이 1인 경우, 

1 -> 2 (문제에서 작은 정점부터 방문한다고 조건이 주어짐.) 

1 -> 3

1 -> 4 

따라서 1 -> 2 -> 3 -> 4

문제 풀이

✔️ DFS 는 재귀를 이용하였고, BFS는 Queue(큐)를 이용하여 문제를 풀었습니다 !

✔️ Scanner 대신 비교적 실행 시간이 짧은 BufferedReader 를 이용하였습니다 !

✔️ String 대신 메모리 사용량이 적고 연산 속도가 빠른 StringBuilder를 이용하였습니다 ! 

 

1. 변수 및 배열 

    static StringBuilder sb = new StringBuilder();
    static int node,line,start;
    static int[][] lines;
    static boolean[] visited;
    static Queue<Integer> q = new LinkedList<>();

• StringBuilder는 bfs, dfs 탐색 결과를 출력하기 위함. 
• node : 정점 갯수, line : 간선 갯수, start : 시작 정점 
• lines : 간선(정점과 정점 사이의 관계) 기록을 위한 배열
• visited : 방문한 정점을 기록하기 위한 배열 
• Queue : BFS 탐색에서 다음으로 탐색 시작할 노드를 찾기위함.
  (예시, 1 -> 2 / 1 -> 3 탐색 후 탐색 할 노드가 더이상 없을 때 노드 2 에서 탐색 다시 시작) 

2. 입력 받기 

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

        //첫 줄 입력 받기(정점, 간선, 시작정점)
        node = Integer.parseInt(st.nextToken());
        line = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(st.nextToken());

        //정점간의 관계를 저장할 배열
        lines = new int[node+1][node+1];
        //방문한 정점 기록용 배열
        visited = new boolean[node+1];

        //간선 입력 받기
        for(int i = 0; i<line; i++){
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            lines[a][b] = lines[b][a] = 1;
        }
 
    }

BufferedReader 와 StringTokenizer 을 이용하여 효율적으로 입력받기 . Scanner 보다 성능이 뛰어나다 !

 

3. dfs 함수 구현 

DFS는 깊이 우선으로 탐색하며, 더 이상 갈 곳이 없을 때 이전 호출 지점으로 돌아가 다른 경로를 탐색합니다.

public static void dfs(int start){
        //방문한 노드 기록하기
        visited[start] = true;
        //출력 stringbuilder에 append
        sb.append(start + " ");

        for(int i = 1; i<= node; i++) {
            if (lines[start][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }

 

[재귀 함수 호출 순서] 

1️⃣dfs(1) 호출

• 인접 노드 2, 3, 4를 검사

2️⃣dfs(2) 호출

• 노드 2 방문
• 인접 노드 1, 4를 검사
  • 노드 1은 이미 방문했으므로 건너뜀
  • 노드 4 방문

3️⃣dfs(4) 호출

• 노드 4 방문
• 인접 노드 1, 2, 3을 검사
  • 노드 1, 2는 이미 방문했으므로 건너뜀
  • 노드 3 방문

4️⃣dfs(3) 호출

• 노드 3 방문
• 인접 노드 1, 4를 검사
  • 모두 이미 방문했으므로 종료

 

• dfs(3) 종료 후, 호출 스택에서 제거되고 dfs(4)로 돌아감.
• dfs(4)의 나머지 for 문을 검사하지만, 모두 이미 방문했으므로 종료.
• dfs(4) 종료 후, 호출 스택에서 제거되고 dfs(2)로 돌아감.
• dfs(2)의 나머지 for 문을 검사하지만, 모두 이미 방문했으므로 종료.
• dfs(2) 종료 후, 호출 스택에서 제거되고 dfs(1)로 돌아감.
• dfs(1)의 나머지 for 문을 검사하지만, 모두 이미 방문했으므로 종료.
• dfs(1) 종료 후, 호출 스택에서 제거되고 탐색 종료.

탐색 종료 시점이 너무 헷갈려서 정리했습니다.. !

재귀 함수는 자신을 다시 호출할 때마다 호출 스택에 새로운 함수 호출이 쌓입니다.

각 호출 스택 프레임은 자신의 로컬 변수를 갖고 있으며, 함수가 종료되면 해당 프레임이 스택에서 제거되고 이전 호출 지점으로 돌아갑니다.

 

3. bfs함수 구현 

Queue 는 FIFO(First-In-First-Out) 원칙을 지닌 자료구조

public static void bfs(int start){
        q.add(start);
        visited[start] = true;

        while(!q.isEmpty()){
        	//탐색 시작 노드 변경
            start = q.poll();
            sb.append(start+ " ");
            for(int i = 1; i<= node; i++){
                if(lines[start][i] == 1 && !visited[i]){
                    q.add(i);
                    visited[i] = true;
                }
            }
        }
    }​

• 시작 노드를 큐에 추가하고 방문 배열을 업데이트합니다.
• 큐가 비어 있지 않은 동안 다음을 반복합니다:
  • 큐에서 노드를 하나 꺼내어 해당 노드를 방문합니다.
  • 해당 노드와 인접한 노드들을 검사하여, 방문하지 않은 노드를 큐에 추가하고 방문 배열을 업데이트합니다.