📌 문제 탐색하기
👉 문제바로가기
N: 정점 개수(1<=N<=1,000)
M: 간선 개수(1<=M<=10,000)
V: 탐색을 시작할 정점의 번호
간선이 연결하는 두 정점의 번호가 주어지면 그래프를 정의하고, V를 정점으로하여 DFS와 BFS를 수행한 결과를 출력하는 문제입니다.
아래는 문제에서 주어진 예제 입력과 출력을 예시로 들어 설명한 것입니다.
1️⃣ 입력 받기
N, M, V = map(int, sys.stdin.readline().split())2️⃣ 그래프 리스트 정의하기
그래프에 원소를 넣기 전에 그래프의 크기를 지정합니다. 그래프의 각 요소가 해당 원소의 인덱스번호 숫자와 연결된 숫자들을 담도록 하기 위한 것이므로, 그래프는 N+1개의 원소를 가집니다. 여기서 N개가 아닌 이유는 0자체가 없을뿐만아니라 0과 연결된 숫자도 없기 때문에 이 숫자를 제외하고 총 N개의 원소가 되기 위해 크기를 N+1로 지정하는 것입니다.
그리고 방문 여부는 초기에 모두 Flase인 상태로 지정합니다. 추후 방문할 때마다 True로 값을 변경하게됩니다.
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)Input받은 정보는 간선이 연결하는 두 정점의 정보입니다. 해당 정보를 통해 우리는 그래프를 정의할 수 있습니다. 그래프는 인접리스트 형태로 구성하였습니다.
- 1은 2와 연결되어 있습니다.
- 1은 3과 연결되어 있습니다.
- 1은 4와 연결되어 있습니다.
- 2는 4와 연결되어 있습니다.
- 3은 4와 연결되어 있습니다.
아래는 인접한 숫자가 무엇인지 한 눈에 볼 수 있는 리스트로 정의한 것이라고 보면 됩니다.
#각 정점들별로 가지고 있는 간선 정보 정렬
graph = [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]]그래프를 기록할 때 인접 행렬 / 인접 리스트 두 가지 방법이 있습니다. 모두 가능하지만 입력 편의성과 탐색 속도를 줄이기위해 인접리스트를 사용했습니다.
🍯 TIP !
DFS / BFS 모두
- 인접 리스트로 탐색하면 O(V+E)
- 인접 행렬로 탐색하면 O(V^2)
이 문제에서 V(정점)은 1,000개, E(간선)은 10,000개로 인접리스트가 유리합니다.
간선의 개수가 많으면 인접행렬이 유리하고, 간선의 개수가 적으면 인접 리스트가 유리합니다.
3️⃣ DFS / BFS 함수 구현
👉 DFS와 BFS함수 구현과 관련된 자세한 내용 참고
DFS
def dfs(start):
visited[start] = True
print(start, end=" ")
#현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[start]:
if not visited[i]:
dfs(i)BFS
한 노드에 대해서 연결된 “같은 깊이의” 노드들을 먼저 탐색합니다. 탐색 중인 노드와 연결된 노드들은 visited=True로 체크하고, 다음 깊이 탐색을 위해 queue에 넣어둡니다.
(연결된 노드와 연결된 다음 노드를 바로 탐색하는 dfs와 달리, bfs는 현재 노드와 연결된 노드들을 먼저 모두 탐색합니다)
이 과정을 queue가 empty가 될 때 까지 반복합니다.
def bfs(start):
queue = deque([start])
visited[start] = True
#큐가 빌 때까지 반복
while queue:
x = queue.popleft()
print(x, end=' ')
#해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for i in graph[x]:
if not visited[i]:
queue.append(i)
visited[i] = True4️⃣ DFS -> BFS 결과 출력
dfs()를 완료하면 visited리스트의 모든 원소 값이 True가 됩니다. 따라서 dfs()를 실행하기 전에 visited값을 한번 더 초기화시켜줍니다.
📌 알고리즘 선택
문제에서 직접적으로 DFS와 BFS를 각각 활용하라고 주어졌으므로 해당 알고리즘을 사용하면 됩니다.
시간복잡도
정렬 부분에서 sort()를 사용하여 정렬하므로 시간복잡도는 O(MlongM)입니다. DFS와 BFS알고리즘 각각은 각 노드를 최대한 한 번씩 모두 방문하고, 각 간선을 최대 한 번씩 탐색하므로 시간복잡도는 O(N+M)입니다. 전체 시간복잡도에 가장 영향을 많이 주는 것은 sort()이고, 전체 시간 복잡도는 O(MlogM+N+M)입니다.
최악의 경우 모든 정점 N개에 대해 O(MlogM)만큼의 시간복잡도가 걸리므로, 최종 시간복잡도는 O(NMlogM)입니다. 총 연산은 약 40,000,000번 필요하고 이는 시간안에 가능한 연산 개수입니다.
📌 코드 설계하기
- N(정점 개수), M(간선 개수), V(탐색을 시작할 정점의 번호)를 Input받습니다.
- 그래프 리스트와 방문 여부를 초기화합니다.
- 간선이 연결하는 두 정점의 정보들을 입력받은 후 그래프 리스트에 값을 정의합니다.
dsf()와bfs()를 구현한 후 해당 알고리즘을 실행한 결과를 출력합니다.
📌 정답 코드
import sys
from collections import deque
def dfs(start):
visited[start] = True
print(start, end=" ")
#현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[start]:
if not visited[i]:
dfs(i)
def bfs(start):
queue = deque([start])
visited[start] = True
#큐가 빌 때까지 반복
while queue:
x = queue.popleft()
print(x, end=' ')
#해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for i in graph[x]:
if not visited[i]:
queue.append(i)
visited[i] = True
N, M, V = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)
for _ in range(M):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
#graph의 각 요소들을 정렬
for i in range(N+1):
graph[i].sort()
dfs(V)
print()
#방문여부 초기화
visited = [False] * (N+1)
bfs(V)