[백준/파이썬] 1260번: DFS와 BFS

문제

https://www.acmicpc.net/problem/1260

DFS란?

DFS(깊이우선탐색)는 최대한 깊이 들어간 뒤 더 이상 갈 곳이 없으면 백트래킹하는 방식으로 동작

특징

• 스택, 재귀 사용
• 한 경로를 끝가지 탐색한 후 다른 경로를 탐색
• 그래프 탐색 시 경로의 깊이가 중요한 경우 적합

동작 과정

1. 시작 노드 방문, 방문 표시
2. 해당 노드의 인접 노드 중 방문하지 않은 노드로 이동
3. 갈 곳이 없으면 이전 노드로 돌아감(백트래킹)
4. 모든 노드를 방문할 때까지 반복

BFS란?

BFS(너비우선탐색)는 현재 노드에서 갈 수 있는 모든 노드를 방문한 후 다음 깊이로 이동하는 방식

특징

• 큐를 사용(FIFO)
• 한 단계씩 이동하면서 모든 인접 노드를 방문 후 다음 단계로 이동
• 최단 경로를 찾는 문제에서 많이 사용됨

동작 과정

1. 시작 노드를 큐에 삽입하고 방문 표시
2. 큐에서 노드를 꺼내고 해당 노드의 인접 노드를 큐에 삽입
3. 모든 노드를 방문할 때까지 반복

비교

비교 항목	DFS	BFS
탐색 방법	최대한 깊이 들어감	같은 깊이 우선 탐색
구현 방법	재귀 or 스택	큐
메모리 사용량	경로 저장을 위해 더 적게 사용	큐를 사용하므로 더 많은 메모리 필요
최단 경로	보장되지 않음	보장
사용 예시	미로 찾기, 백트래킹	최단 경로 문제, 네트워크 탐색

풀이

• DFS, BFS 구현 문제

예제 분석

4 5 1 # 정점 4개, 간선 5개, 시작 정점 1
1 2
1 3
1 4
2 4
3 4

인접 행렬

   1  2  3  4
1 [0, 1, 1, 1]
2 [1, 0, 0, 1]
3 [1, 0, 0, 1]
4 [1, 1, 1, 0]

• graph[1][2] = 1 1과 2가 연결
• graph[1][3] = 1 1과 3가 연결
• graph[1][4] = 1 1과 4가 연결
• ...

DFS 탐색 과정

시작 정점: 1
1️⃣ 1번 방문 -> visitied[1] = 1
-> graph[1][2] == 1 이고 visited[2] == 0이므로 2번 이동
2️⃣ 2번 방문 → visited[2] = 1
→ graph[2][1] == 1이지만 visited[1] == 1이므로 건너뜀
→ graph[2][4] == 1이고 visited[4] == 0이므로 4번으로 이동
3️⃣ 4번 방문 → visited[4] = 1
→ graph[4][1] == 1이지만 visited[1] == 1이므로 건너뜀
→ graph[4][2] == 1이지만 visited[2] == 1이므로 건너뜀
→ graph[4][3] == 1이고 visited[3] == 0이므로 3번으로 이동
4️⃣ 3번 방문 → visited[3] = 1
→ graph[3][1] == 1이지만 visited[1] == 1이므로 건너뜀
→ graph[3][4] == 1이지만 visited[4] == 1이므로 건너뜀
→ 더 이상 탐색할 노드가 없으므로 종료

BFS 탐색 과정

시작 정점: 1
1️⃣ 1번 방문 → queue = [1], visited[1] = 1
graph[1][2] == 1, visited[2] == 0 → 2번 큐에 추가
graph[1][3] == 1, visited[3] == 0 → 3번 큐에 추가
graph[1][4] == 1, visited[4] == 0 → 4번 큐에 추가
현재 큐 상태: [2, 3, 4]
2️⃣ 2번 방문 (queue.popleft())
graph[2][4] == 1, visited[4] == 1 (이미 방문) → 건너뜀
현재 큐 상태: [3, 4]
3️⃣ 3번 방문 (queue.popleft())
graph[3][4] == 1, visited[4] == 1 (이미 방문) → 건너뜀
현재 큐 상태: [4]
4️⃣ 4번 방문 (queue.popleft())
모든 연결된 노드가 이미 방문됨 → 종료
현재 큐 상태: [] (큐가 비어있음)

이제 분석이 끝났으니 코드를 작성해볼게요.

DFS와 BFS 구현에 필요한 graph 배열과 visited 배열을 선언해줍니다.

n,m,v = map(int,input().split()) # 정점 개수, 간선 개수, 시작 정점
graph = [[0]*(n+1) for _ in range(n+1)] # 인접 행렬
visited = [0] * (n+1) # 방문 기록 표시

# 그래프 정보 입력
for i in range(m):
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1 # 양방향 그래프

다음으로 DFS를 수행할 함수를 선언해줍니다.

def dfs(v):
    visited[v] = 1 # 방문 표시
    print(v, end=" ") # 출력
    for i in range(1,n+1): # 1번부터 n번까지 노드 탐색
        if graph[v][i] == 1 and visited[i] == 0: # 연결된 노드 && 방문하지 않은 노드
            dfs(i)

1. 정점 v에서 i로 이동할 수 있는지 검사 (v와 i가 연결되었으면 1)
2. 정점 i를 방문했는지 검사 (방문하지 않았으면 0)

# 출력
1 2 4 3

올바르게 출력이 되네요.

다음으로 BFS를 선언해보겠습니다.

def bfs(v):
    queue = deque([v])
    visited2[v] = 1

1. 시작 정점을 큐에 추가
2. 방문 처리

    while queue:
        node = queue.popleft()
        print(node, end=" ")

3. queue에 아무것도 남아있지 않을 때까지 반복
4. 방문한 노드 출력

        for i in range(1,n+1):
            if graph[node][i] == 1 and visited2[i] == 0:
                queue.append(i)
                visited2[i] = 1

5. 1번 정점부터 n번 정점까지 확인
6. 연결된 노드 검사 && 방문했는지 검사
7. 조건이 일치한다면 queue에 i 추가
8. i 방문 처리

코드

from collections import deque
import sys
input = sys.stdin.readline

def dfs(v):
    visited[v] = 1
    print(v, end=" ")
    for i in range(1,n+1):
        if graph[v][i] == 1 and visited[i] == 0:
            dfs(i)

def bfs(v):
    queue = deque([v])
    visited2[v] = 1
    while queue:
        node = queue.popleft()
        print(node, end=" ")
        for i in range(1,n+1):
            if graph[node][i] == 1 and visited2[i] == 0:
                queue.append(i)
                visited2[i] = 1

if __name__ == "__main__":
    n,m,v = map(int,input().split())
    graph = [[0]*(n+1) for _ in range(n+1)]
    visited = [0] * (n+1)
    visited2 = visited.copy()

    for i in range(m):
        a,b = map(int,input().split())
        graph[a][b] = graph[b][a] = 1

    dfs(v)
    print()
    bfs(v)