๋ฌธ์ ๋งํฌ
https://www.acmicpc.net/problem/1260
1260๋ฒ: DFS์ BFS
์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N(1 ≤ N ≤ 1,000), ๊ฐ์ ์ ๊ฐ์ M(1 ≤ M ≤ 10,000), ํ์์ ์์ํ ์ ์ ์ ๋ฒํธ V๊ฐ ์ฃผ์ด์ง๋ค. ๋ค์ M๊ฐ์ ์ค์๋ ๊ฐ์ ์ด ์ฐ๊ฒฐํ๋ ๋ ์ ์ ์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค. ์ด๋ค ๋ ์ ์ ์ฌ
www.acmicpc.net
๋์ ํ์ด
dfs/bfs๋ฅผ ํ์ฉํ ์ฝ๋๋ฅผ ํ์ด๋ณด์ง ์์์ ์ฐธ๊ณ ์๋ฃ๋ฅผ ํ์ฉํด ๋ฌธ์ ๋ฅผ ํ์ด๋ณด๋ ์๊ฐ์ ๊ฐ์ก๋ค. ์ง๊ธ์ ๋จ์ํ ๊ทธ๋ํ๋ฅผ ํ์ํ๋ ๋ฌธ์ ๋ฅผ ํ์์ง๋ง, ์์ผ๋ก๋ ์์ฉ๋ฌธ์ ๋ฅผ ๊ณ์ ํ์ด๋ณด๋ฉด์ LG CNS ์ฝํ ์ ๊น์ง bfs, dfs๋ฅผ ์ ๋ณตํ๋๊ฒ ๋ชฉํ๋ค. ๊ผญ dfs/bfs๋ฌธ์ ๋ ํ๊ณ ๋์ค๋ฆฌ๋ผ!
bfs, dfs์ ์ ๋ง ๊ฐ๋จํ ๊ฐ๋
) https://didu-story.tistory.com/98?category=902867
๋ด๊ฐ ์ฐธ๊ณ ํ ์๋ฃ ) https://itholic.github.io/python-bfs-dfs/
[์๊ณ ๋ฆฌ์ฆ] ํ์ ์๊ณ ๋ฆฌ์ฆ DFS, BFS
-- ๋ณธ ํฌ์คํ ์ ์ด๊ฒ์ด ์ทจ์ ์ ์ํ ์ฝ๋ฉ ํ ์คํธ๋ค with ํ์ด์ฌ ์ฑ ์ ์ฐธ๊ณ ํ์ฌ ์์ฑ๋์์ต๋๋ค. 1. DFS Depth First Search, ๊น์ด ์ฐ์ ํ์ ๊ทธ๋ํ์ ๊น์ ๋ถ๋ถ์ ์ฐ์ ์ ์ผ๋ก ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ ์ฃผ๋ก ์ค
didu-story.tistory.com
from collections import deque
N,M,V=map(int,input().split())
matrix=[[0]*(N+1) for i in range(N+1)]
for i in range(M):
a, b = map(int, input().split())
matrix[a][b] = matrix[b][a] = 1
visited = [0] * (N+1)
############์
๋ ฅ ํ์ ์ธ์ฐ๊ธฐ############
def dfs(v):
#์์๋
ธ๋๋ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ ๋ถํฐ ํ๊ณ ์์
visited[v] = 1
print(v, end=' ')
for i in range(1, N+1):
# matrix[v][i] ๋ฅผ ์ฐ๋ ์ด์ ๋ ์ธ์ ํ๋ ฌ ์ค, visited=0์ธ๊ฑฐ ์ฐพ๋๊ฑฐ์
# ๋ง์ฝ ์ธ์ ํ๋ ฌ์ด ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋๋ผ๋ฉด, ๋ฐฉ๋ฌธํด์ dfs์ฌ๊ท๋ก ๋๋ ค์ฃผ๊ธฐ
if (visited[i]==0 and matrix[v][i]==1):
dfs(i)
def bfs(v):
queue = deque([v])
#๋ฌธ์ ๊ฐ dfs๋จผ์ ๋๋ฆฌ๊ณ bfs๋๋ฆฌ๋ ๊ฒ
#๋ฐ๋ผ์ dfs๋์๊ฐ๋ฉด์ ๋ฐฉ๋ฌธ๋
ธ๋๋ฅผ 1๋ก ๋ฐ๊พธ์์ผ๋๊น ์ฌ๊ธฐ์ 0์ผ๋ก ๋ฐ๊ฟ์ฃผ๋ฉด์ ๋ฐฉ๋ฌธ
visited[v] = 0
#๋ฐฉ๋ฌธํ ๋
ธ๋๋ฅผ queue์ ๋ฃ์ด์ฃผ๊ณ ์ด๋ํ ๊ฑด๋ฐ ์ฌ๊ธฐ queue์ ์๋ฌด๊ฒ๋ ์์๋๊น์ง ์งํ
#์์๋
ธ๋v๋ฅผ queue์ ๋ฃ๊ณ ์์
while queue:
v = queue.popleft()
print(v, end=' ')
for i in range(1, N+1):
#visited๊ฐ ์์ง 1์ด๊ณ , ์ธ์ ํ๋ ฌ์ด ์๋ค๋ฉด ๋ฐฉ๋ฌธํด์ค์ผํ๋๊น queue์ ๋ฃ๊ณ ๋ฐฉ๋ฌธ์ฒ๋ฆฌํด์ค
if (visited[i]==1 and matrix[v][i]==1):
queue.append(i)
visited[i] = 0
dfs(V)
print()
bfs(V)