1260번: DFS와 BFS(9 / 3) - 실버 2

문제

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

입력

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

출력

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

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1

1 2 4 3
1 2 3 4

예제 입력 2

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2

3 1 2 5 4
3 1 4 2 5

예제 입력 3

1000 1 1000
999 1000

예제 출력 3

1000 999
1000 999

코드

import sys
from collections import deque

# 정점의 개수 n, 간선의 개수 m, 시작할 정점의 번호 v 를 입력
n, m, v = map(int, sys.stdin.readline().split())

# 잘못된 그래프 초기화
# graph = [[]] + [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

# 올바른 그래프 초기화
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

# 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것부터 방문하도록 정렬
for i in range(1, n + 1):
    graph[i].sort()

# 정점의 개수 만큼
visited = [False] * (n + 1)

# DFS
def dfs_function(v):
    # 해당 노드 방문 처리
    visited[v] = True
    print(v, end=' ')

    for i in graph[v]:
        if not visited[i]:
            dfs_function(i)

def bfs_function(start):
    # 시작 정점을 큐에 넣음
    queue = deque([start])
    visited[start] = True

    while queue:
        # 큐에서 가장 앞에 있는 정점을 꺼낸다.
        v = queue.popleft()
        print(v, end=' ')

        # 해당 정점에 연결된 정점들을 탐색한다.
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

dfs_function(v)
visited = [False] * (n + 1)
print()
bfs_function(v)

코드 풀이

1. n, m, v = map(int, sys.stdin.readline().split())
   • n은 정점의 개수, m은 간선의 개수, v는 시작할 정점의 번호를 입력받는다.
2. graph 초기화
   • graph = [[] for _ in range(n + 1)]
     • 어떠한 노드가 연결되어 있는지를 파악하기 위해 각 노드 + 1만큼 리스트를 만든다.
     • n + 1을 한 이유는 사용하지 않는 0번째 리스트를 만들기 위해서이다.
   • a, b = map(int, sys.stdin.readline().split())
     • 각 연결된 노드를 입력으로 받는다.
     • a와 b는 서로 연결되어 있다는 의미이므로 graph의 각 위치에 append를 한다.
   • graph[i].sort()
     • 1부터 n + 1번 째까지 루프를 돌며 graph[i]를 오름차순 정렬한다.
     • 방문할 수 있는 노드가 여러 개인 경우, 예를 들어 [2, 3, 4]인 경우 작은 것 부터 방문하라는 문제의 지시사항 때문에 오름차순 정렬을 한다.

# 올바른 그래프 초기화
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

# 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것부터 방문하도록 정렬
for i in range(1, n + 1):
    graph[i].sort()

1. dfs_function을 정의한다.
   • 깊이 우선 탐색의 경우 재귀함수를 사용한다. (스택 자료 구조)
   • visited[i] = True
     • 인자로 들어온 노드를 방문 처리 한다,
   • 해당 인자의 graph를 for 루프를 돌며 방문하지 않은 경우 재귀함수 인자에 노드를 인자로 전달함
2. bfs_function을 정의한다.
   • 너비 우선 탐색의 경우 큐를 사용한다.
   • 파이썬에서는 collections 라이브러리의 deque를 사용한다.
   • queue = deque([start])
     • queue를 초기화 하자마자 시작할 노드를 queue에 넣는다.
   • visited[start] = True
     • queue에 넣고 방문 처리를 한다.
   • while queue:
     • queue가 없을 때까지 반복한다.
   • v = queue.popleft()
     • 큐의 가장 처음에 들어온 노드를 꺼내고 v 변수에 전달한다.
   • for i in graph[v]:
     • 해당 노드와 연결된 다른 정점들을 너비 우선 탐색으로 방문하기 위해 for 루프를 돈다.
   • queue.append(i)
     • 만약에 방문처리가 되지 않았다면, 해당 노드를 큐에 넣는다.
   • visited[i] = True
     • 큐에 넣고 방문처리를 한다.
3. dfs에서 visite가 False에서 True로 변경 되어 있으므로 다시 visited를 초기화한다.

핵심 포인트

1. 가장 중요한 핵심 포인트는 어떠한 노드끼리 연결 되었는지 나타내는 입력이 주어졌을 때, 2차원 graph로 만드는 것이다.

# graph 초기화 - 빈 리스트를 초기화하여 어떤 정점이 연결 되어있는지 파악
graph = [[] for _ in range(n + 1)]

# input을 받으면서 각 정점이 어떤 정점과 연결되어 있는지 graph에 추가
# 1, 2라면, 1 정점은 2와 연결 되어 있고 2 정점은 1 정점과 연결돼 있다
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

1. 문제의 요구사항에 맞게 방문할 정점이 2개인 경우, 오름차순 정렬을 한다.

# 0은 사용하지 않는 빈 리스트이므로 1부터 start
for i in range(1, n + 1):
		graph[i].sort()

1. dfs는 재귀함수를 사용하고, bfs는 큐(deque)를 사용하여 함수를 정의한다.

BFS 동작 원리

BFS는 큐 자료 구조를 사용한다.

1. 시작 정점을 큐에 삽입한다.
   • 탐색을 시작할 정점을 큐에 넣는다.
   • 이때 해당 정점을 방문했다고 표시한다.
2. 큐에서 정점을 꺼내고, 인접한 정점을 큐에 삽입한다.
   • 큐에서 정점을 꺼내 그 정점에 인접한 정점을 모두 방문한다. 인접한 정점 중 아직 방문하지 않은 정점들은 큐에 넣고, 방문했다고 표시한다.
3. 큐가 빌 때까지 반복한다.
   • 큐가 빌 때까지 이 과정을 반복한다. 이때 BFS는 큐의 특성상 먼저 삽입된 정점(가까운 정점)부터 탐색을 진행한다.

BFS 구현

• BFS는 큐를 사용해서 구현한다. 파이썬에서는 from collections import deque를 사용하여 큐를 쉽게 구현할 수 있다.

올바른 그래프 초기화 방법

각 정점에 대해 연결된 정점들의 리스트를 별도로 관리한다. (각 정점의 연결 관계를 명확히 표현해야 함.)

1. graph = [[] for _ in range(정점 + 1)] 은 정점 + 1개의 빈 리스트를 가지는 리스트를 생성한다. 이렇게 하면 각 정점에 대해 연결된 정점들의 리스트를 따로 유지할 수 있다.
2. 이후 for _ in range(간선) 루프에서 간선 정보를 입력받아 각 정점의 인접 리스트에 연결된 정점을 추가한다. 예를 들어, 정점 a와 b가 연결 되어 있으면 graph[a].append(b)와 graph[b].append(a) 를 통해 양방향으로 간선을 추가한다.
3. 마지막으로 for i in range(1, 정점 + 1): graph[i].sort() 를 통해 각 정점의 인접 리스트를 오름차순 정렬하여, DFS와 BFS에서 정점 번호가 작은 것부터 방문하도록 보장한다.

잘못된 그래프 초기화 방법

간선 정보를 그대로 저장하는 리스트를 생성하여 정점 간의 연결 관계를 명확하게 나타내지 않는다.

이렇게 되면 특정 정점이 어떤 정점과 연결되어 있는지 알기 어려우며, 그래프 구조 자체가 올바르게 표현되지 않는다.

graph = [[]] + [list(map(int, sys.stdin.readline().split())) for _ in range(m)] - 잘못된 방법