나한나한나한나

문제

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

---

 

답

from collections import deque

def dfs(graph, start, visited):
    visited[start] = True
    print(start, end=' ')

    for neighbor in sorted(graph[start]):
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

def bfs(graph, start):
    visited = [False] * (N + 1)
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')

        for neighbor in sorted(graph[v]):
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True

# 입력 받기
N, M, V = map(int, input().split())
graph = [[] for _ in range(N + 1)]

# 그래프 구성
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# DFS 실행
visited = [False] * (N + 1)
dfs(graph, V, visited)
print()

# BFS 실행
bfs(graph, V)

---

그래프가 어떤 식으로 구성되고 출력되는가?

예제 입력 1을 사용하여 설명

예제 입력 1
4 5 1
1 2
1 3
1 4
2 4
3 4

 

1. 그래프 초기화:(인덱스 0은 사용하지 않음)

graph = [[], [], [], [], []]

 

2. 간선 정보 입력 후 그래프 구성

graph = [
    [],
    [2, 3, 4],  # 정점 1의 인접 정점
    [1, 4],     # 정점 2의 인접 정점
    [1, 4],     # 정점 3의 인접 정점
    [1, 2, 3]   # 정점 4의 인접 정점
]

 

3. DFS 실행 과정: 시작 정점 1

방문: 1
│
└─→ 방문: 2
    │
    └─→ 방문: 4
        │
        └─→ 방문: 3

 

4. BFS 실행 과정: 시작 정점 1

큐: [1]
방문: 1
│
├─→ 방문: 2
│
├─→ 방문: 3
│
└─→ 방문: 4

 

도식화:

    2
   / \
  1---4
   \ /
    3

 

 

DFS 진행 순서:

1. 1 방문 (출력)
2. 1의 인접 정점 중 가장 작은 2 방문 (출력)
3. 2의 인접 정점 중 아직 방문하지 않은 가장 작은 4 방문 (출력)
4. 4의 인접 정점 중 아직 방문하지 않은 가장 작은 3 방문 (출력)
5. 모든 정점 방문 완료

BFS 진행 순서:

1. 1 방문 (출력) 및 큐에 1의 인접 정점 추가 [2, 3, 4]
2. 큐에서 2 꺼내어 방문 (출력)
3. 큐에서 3 꺼내어 방문 (출력)
4. 큐에서 4 꺼내어 방문 (출력)
5. 큐 비어있음, 종료

이 과정을 통해 DFS는 깊이 우선으로, BFS는 너비 우선으로 그래프를 탐색하며 각각의 결과를 출력하게 됩니다.