๐ ์ถ์ฒ - 1260 - DFS์ BFS
๋ฌธ์ ์ค๋ช
๊ทธ๋ํ๋ฅผ DFS๋ก ํ์ํ ๊ฒฐ๊ณผ์ BFS๋ก ํ์ํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋จ, ๋ฐฉ๋ฌธํ ์ ์๋ ์ ์ ์ด ์ฌ๋ฌ ๊ฐ์ธ ๊ฒฝ์ฐ์๋ ์ ์ ๋ฒํธ๊ฐ ์์ ๊ฒ์ ๋จผ์ ๋ฐฉ๋ฌธํ๊ณ , ๋ ์ด์ ๋ฐฉ๋ฌธํ ์ ์๋ ์ ์ด ์๋ ๊ฒฝ์ฐ ์ข
๋ฃํ๋ค. ์ ์ ๋ฒํธ๋ 1๋ฒ๋ถํฐ N๋ฒ๊น์ง์ด๋ค.
์
๋ ฅ
์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N(1 โค N โค 1,000), ๊ฐ์ ์ ๊ฐ์ M(1 โค M โค 10,000), ํ์์ ์์ํ ์ ์ ์ ๋ฒํธ V๊ฐ ์ฃผ์ด์ง๋ค. ๋ค์ M๊ฐ์ ์ค์๋ ๊ฐ์ ์ด ์ฐ๊ฒฐํ๋ ๋ ์ ์ ์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค. ์ด๋ค ๋ ์ ์ ์ฌ์ด์ ์ฌ๋ฌ ๊ฐ์ ๊ฐ์ ์ด ์์ ์ ์๋ค. ์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ๊ฐ์ ์ ์๋ฐฉํฅ์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ DFS๋ฅผ ์ํํ ๊ฒฐ๊ณผ๋ฅผ, ๊ทธ ๋ค์ ์ค์๋ BFS๋ฅผ ์ํํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ค. V๋ถํฐ ๋ฐฉ๋ฌธ๋ ์ ์ ์์๋๋ก ์ถ๋ ฅํ๋ฉด ๋๋ค.
์ ์ถ๋ ฅ ์
์์ ์ ๋ ฅ | ์์ ์ถ๋ ฅ |
---|---|
4 5 1 1 2 1 3 1 4 2 4 3 4 | 1 2 4 3 1 2 3 4 |
5 5 3 5 4 5 2 1 2 3 4 3 1 | 3 1 2 5 4 3 1 4 2 5 |
1000 1 1000 999 1000 | 1000 999 1000 999 |
Logic 1. DFS
1. ๋ฐฉ๋ฌธ ๋ ธ๋ ์ฒดํน
2. ๋ฐฉ๋ฌธ ๋ ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ ธ๋๊ฐ ์๊ณ , ๋ฐฉ๋ฌธํ์ง ์์๋ค๋ฉด ๋ฐฉ๋ฌธ
3. 2๋ฒ ๋ฐ๋ณต
Logic 2. BFS
1. queue(deque) ์์ฑ
2. queue์ ์์ ๋ ธ๋๋ฅผ ๋ด์์ฃผ๊ณ , ๋ฐฉ๋ฌธ ๋ ธ๋ ์ฒดํน
3. queue๊ฐ ๋น ๋ ๊น์ง ๋ฐ๋ณต
4. queue์์ ํ๋์ ์์๋ฅผ ๊บผ๋ด๊ณ
5. ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ์ธ์ ํ ๋ ธ๋๊ฐ ์๋ค๋ฉด queue์ ์ฝ์
from collections import deque
def bfs(v):
queue = deque()
queue.append(v)
visited2[v] = 1
while queue:
v = queue.popleft()
print(v, end = ' ')
for i in range(1, N+1):
# ๋ฐฉ๋ฌธํ์ง ์์๊ณ , ๋
ธ๋๊ฐ ์ฐ๊ฒฐ๋์ด ์๋ค๋ฉด ์ธ์ ๋
ธ๋ ๋ชจ๋ ์ถ๊ฐ
if visited2[i] == 0 and graph[v][i] == 1:
queue.append(i)
visited2[i] = 1
def dfs(graph, V, visited):
# ํ์ฌ ๋
ธ๋ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ
visited[V] = True
print(V, end = ' ')
# ํ์ฌ ๋
ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ๋
ธ๋๋ฅผ ์ฌ๊ท์ ์ผ๋ก ๋ฐฉ๋ฌธ
for i in range(1, N+1):
if not visited[i] and graph[V][i] == 1:
dfs(graph, i, visited)
N, M, V = map(int, input().split())
graph = [[0] * (N+1) for _ in range(N+1)]
# ๊ฐ์
for i in range(M):
a, b = map(int, input().split())
graph[a][b] = graph[b][a] = 1
# ๊ฐ ๋
ธ๋๊ฐ ๋ฐฉ๋ฌธ๋ ์ ๋ณด ํํ
visited = [False] * (N+1)
visited2 = [False] * (N+1)
dfs(graph, V, visited)
print()
bfs(V)
๊น์ด ์ฐ์ ํ์์ด๋ผ๊ณ ๋ ๋ถ๋ฆฌ๋ DFS๋ ์ต๋ํ ๊น์ด ๋ด๋ ค๊ฐ ๋ค, ๋์ด์ ๊น์ด ๊ฐ ๊ณณ์ด ์์ ๊ฒฝ์ฐ ์์ผ๋ก ์ด๋ํด ํ์
ํ๋ ๋ฐฉ์์ ์ด์ผ๊ธฐํฉ๋๋ค.
๋ฃจํธ ๋ ธ๋(ํน์ ๋ค๋ฅธ ์์์ ๋ ธ๋)์์ ์์ํด ๋ค์ ๋ถ๊ธฐ(branch)๋ก ๋์ด๊ฐ๊ธฐ ์ ์ ํด๋น ๋ถ๊ธฐ๋ฅผ ์๋ฒฝํ๊ฒ ํ์ํ๋ ๋ฐฉ์์ ์ด์ผ๊ธฐํฉ๋๋ค.
# DFS ํจ์ ์ ์
def dfs(graph, v, visited):
# ํ์ฌ ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ
visited[v] = True
print(v, end=' ')
# ํ์ฌ ๋
ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ๋
ธ๋๋ฅผ ์ฌ๊ท์ ์ผ๋ก ๋ฐฉ๋ฌธ
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
# ๊ฐ ๋
ธ๋๊ฐ ์ฐ๊ฒฐ๋ ์ ๋ณด๋ฅผ ๋ฆฌ์คํธ ์๋ฃํ์ผ๋ก ํํ(2์ฐจ์ ๋ฆฌ์คํธ)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# ๊ฐ ๋
ธ๋๊ฐ ๋ฐฉ๋ฌธ๋ ์ ๋ณด๋ฅผ ๋ฆฌ์คํธ ์๋ฃํ์ผ๋ก ํํ(1์ฐจ์ ๋ฆฌ์คํธ)
visited = [False] * 9
# ์ ์๋ DFS ํจ์ ํธ์ถ
dfs(graph, 1, visited)
๋๋น ์ฐ์ ํ์์ด๋ผ๊ณ ๋ ๋ถ๋ฆฌ๋ BFS๋ ์ต๋ํ ๋๊ฒ ์ด๋ํ ๋ค์, ๋ ์ด์ ๊ฐ ์ ์์ ๋ ์๋๋ก ์ด๋ํด ํ์
ํ๋ ๋ฐฉ์์ ์ด์ผ๊ธฐํฉ๋๋ค.
๋ฃจํธ ๋ ธ๋(ํน์ ๋ค๋ฅธ ์์์ ๋ ธ๋)์์ ์์ํด ์ธ์ ํ ๋ ธ๋๋ฅผ ๋จผ์ ํ์ํ๋ ๋ฐฉ๋ฒ์ผ๋ก, ์์ ์ ์ ์ผ๋ก๋ถํฐ ๊ฐ๊น์ด ์ ์ ์ ๋จผ์ ๋ฐฉ๋ฌธํ๊ณ ๋ฉ๋ฆฌ ๋จ์ด์ ธ ์๋ ์ ์ ์ ๋์ค์ ๋ฐฉ๋ฌธํ๋ ์ํํ๋ ๋ฐฉ๋ฒ์ ๋๋ค.
์ฃผ๋ก ๋ ๋ ธ๋ ์ฌ์ด์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๊ณ ์ถ์ ๋ ์ด ๋ฐฉ๋ฒ์ ์ ํํฉ๋๋ค.
ex) ์ง๊ตฌ ์์ ์กด์ฌํ๋ ๋ชจ๋ ์น๊ตฌ ๊ด๊ณ๋ฅผ ๊ทธ๋ํ๋ก ํํํ ํ Sam๊ณผ Eddie์ฌ์ด์ ์กด์ฌํ๋ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๊ฒฝ์ฐ
from collections import deque
# BFS ํจ์ ์ ์
def bfs(graph, start, visited):
# ํ(Queue) ๊ตฌํ์ ์ํด deque ๋ผ์ด๋ธ๋ฌ๋ฆฌ ์ฌ์ฉ
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
# ๊ฐ ๋
ธ๋๊ฐ ์ฐ๊ฒฐ๋ ์ ๋ณด๋ฅผ ๋ฆฌ์คํธ ์๋ฃํ์ผ๋ก ํํ(2์ฐจ์ ๋ฆฌ์คํธ)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# ๊ฐ ๋
ธ๋๊ฐ ๋ฐฉ๋ฌธ๋ ์ ๋ณด๋ฅผ ๋ฆฌ์คํธ ์๋ฃํ์ผ๋ก ํํ(1์ฐจ์ ๋ฆฌ์คํธ)
visited = [False] * 9
# ์ ์๋ BFS ํจ์ ํธ์ถ
bfs(graph, 1, visited)
DFS(๊น์ด ์ฐ์ ํ์) | BFS(๋๋น ์ฐ์ ํ์) |
---|---|
ํ์ฌ ์ ์ ์์ ๊ฐ ์ ์๋ ์ ๋ค๊น์ง ๋ค์ด๊ฐ๋ฉด์ ํ์ | ํ์ฌ ์ ์ ์ ์ฐ๊ฒฐ๋ ๊ฐ๊น์ด ์ ๋ค๋ถํฐ ํ์ |
์คํ ๋๋ ์ฌ๊ทํจ์๋ก ๊ตฌํ | ํ๋ฅผ ์ด์ฉํด์ ๊ตฌํ |
๐ก DFS์ BFS์ ์๊ฐ๋ณต์ก๋
๋ ๋ฐฉ์ ๋ชจ๋ ์กฐ๊ฑด ๋ด์ ๋ชจ๋ ๋ ธ๋๋ฅผ ๊ฒ์ํ๋ค๋ ์ ์์ ์๊ฐ ๋ณต์ก๋๋ ๋์ผํฉ๋๋ค.
DFS์ BFS ๋ ๋ค ๋ค์ ๋ ธ๋๊ฐ ๋ฐฉ๋ฌธํ์๋์ง๋ฅผ ํ์ธํ๋ ์๊ฐ๊ณผ ๊ฐ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๋ ์๊ฐ์ ํฉํ๋ฉด ๋ฉ๋๋ค.
N์ ๋ ธ๋, E๋ ๊ฐ์ ์ผ ๋
์ธ์ ๋ฆฌ์คํธ : O(N+E)
์ธ์ ํ๋ ฌ : O(Nยฒ)
์ผ๋ฐ์ ์ผ๋ก E(๊ฐ์ )์ ํฌ๊ธฐ๊ฐ Nยฒ์ ๋นํด ์๋์ ์ผ๋ก ์ ๊ธฐ ๋๋ฌธ์ ์ธ์ ๋ฆฌ์คํธ ๋ฐฉ์์ด ํจ์จ์ ์ด๋ค.
์ฐธ๊ณ ์๋ฃ ๐ฉ