[BOJ][DFS/BFS] 1260. DFS와 BFS (java / python)

✏️ 문제

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

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

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

 

🔢 알고리즘

 

#그래프  #DFS   #BFS

 

 

🤯 풀이 방법

DFS는 스택, BFS는 큐를 이용해서 구현한다.

주의 사항

 - 무방향 그래프이므로 양쪽 방향을 모두 체크해준다 (인접 행렬의 경우는 행/열 순서 바꿔서 체크해주면 됨)

 - DFS는 선입후출이므로 문제 조건인 순서대로 방문을 위해서는 인덱스를 뒤에서부터 탐색해서 스택에 넣어주어야 함

 

👾 구현 코드 (자바)

import java.util.*;
import java.io.*;

public class Main
{
    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());   // 탐색 시작 정점

        // 그래프 구현: 인접 행렬 사용
        int[][] graph = new int[N + 1][N + 1];  // 정점은 1부터 시작
        for (int i = 0; i < M; i++) {   // 간선의 개수만큼 입력받는다
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            graph[start][end] = 1;
            graph[end][start] = 1;
        }

        // 1. DFS: 스택 사용
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] v1 = new int[N + 1];
        Stack<Integer> stack = new Stack<>();
        stack.push(V);
        while (!stack.isEmpty()) {  // 스택이 빌 때까지 탐색
            int cur = stack.pop();  // 가장 위의 노드 출력
            if (v1[cur] != 1) {
                v1[cur] = 1;
                for (int j = N; j > 0; j--) { // 역순으로 추가하여 낮은 번호가 먼저 처리되도록
                    if (graph[cur][j] == 1 && v1[j] == 0) {
                        stack.push(j);
                    }
                }
                bw.write(cur + " ");
            }
        }
        bw.flush();
        System.out.println();

        // 2. BFS
        Queue<Integer> q = new LinkedList<>();
        int[] v2 = new int[N + 1];
        q.add(V);
        while (!q.isEmpty()) {
            int cur = q.poll();
            if (v2[cur] != 1) {
                v2[cur] = 1;
                for (int j = 1; j <= N; j++) {
                    if (graph[cur][j] == 1 && v2[j] == 0) {
                        q.add(j);
                    }
                }
                bw.write(cur + " ");
            }
        }
        bw.flush();
        bw.close();
    }
}

 

 

🤖 GPT의 개선 제안

 

• 함수 분리:
  • DFS와 BFS를 각각 함수로 분리하여 재사용성과 가독성 향상
• 방문 배열 관리:
  • 각 탐색 함수가 독립적으로 방문 배열을 처리하도록 설계
• 출력 방식 개선:
  • BufferedWriter를 함수의 매개변수로 전달
• 스택과 큐 최적화:
  • 방문 처리를 스택/큐에 추가하는 시점에서 수행하여 중복 처리를 방지

 

// DFS 실행
boolean[] visitedDFS = new boolean[N + 1];
dfs(V, graph, visitedDFS, bw);
bw.newLine();

// BFS 실행
boolean[] visitedBFS = new boolean[N + 1];
bfs(V, graph, visitedBFS, bw);
bw.newLine();

bw.flush();
bw.close();

 

 

 

---

+)

👾 구현 코드 (파이썬)

def dfs(v):
    visited[v] = 1
    print(v, end=' ')
    for i in arr[v]:
        if visited[i] == 0:
            dfs(i)

def bfs(v):
    q = []
    q.append(v)
    visited[v] = 1
    while q:
        i = q.pop(0)
        print(i, end=" ")
        for j in arr[i]:
            if visited[j] == 0:
                q.append(j)
                visited[j] = 1

N, M, V = map(int, input().split())
arr = [list() for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)


for i in range(N + 1):
    arr[i].sort()


visited = [0] * (N + 1)
dfs(V)

print()

visited = [0] * (N + 1)
bfs(V)