[Baekjoon] 1260 - DFS와 BFS

📝 문제

 

 

❗ 주의

① 문제의 조건 중

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문

→ 나 같은 경우는 인접행렬을 사용해서 큰 상관이 없었지만,

인접리스트를 사용하는 경우 정렬 과정이 필요하다.

 

② DFS 수행 후, BFS 수행 전에 방문배열을 꼭 초기화 해주어야 한다.

 

 

🔑 풀이 과정

기본적인 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;

public class Main {

    static int[][] A;
    static boolean[] visited;

    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());

        A = new int[N+1][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());

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

        // --- 입력 종료
        visited = new boolean[N+1];
        DFS(V);
        System.out.println();

        visited = new boolean[N+1];
        BFS(V);

    }

    static void DFS(int s){
        if(visited[s]){
            return;
        } else{
            visited[s] = true;
            System.out.print(s + " ");
            for(int i = 1; i < A[s].length; i++){
                if(A[s][i] == 1)
                    DFS(i);
            }
        }
    }

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

        while(!queue.isEmpty()){
            int n = queue.poll();
            System.out.print(n + " ");
            for(int i = 1; i < A[s].length; i++){
                if((A[n][i] == 1) && (visited[i] == false)){
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }

    }

}

 

 

 

🖤 알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색

- 깊이 우선 탐색