1260 DFS와 BFS _python

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

1260번: DFS와 BFS

정석이네

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

말그대로 DFS와 BFS를 사용하는 문제다.

검색해보니 dfs를 재귀로 푼 블로그가 많던데, 재귀는 죽어도 쓰기 싫어서 그냥 while문으로 풀었다.

간선은 2차원배열로 생성했다. a, b 를 입력받았다면 [a][b]와 [b][a]를 둘 다 간선이 있다고 체크해야한다. 양방향이기 떄문.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

 

from collections import deque
import sys
input = sys.stdin.readline

"""

"""

def DFS(N, edges, V):
    visited = [False]*(N+1)
    stack = [V]
    answer = []

    while stack:
        num = stack.pop()
        if visited[num]:
            continue
        answer.append(num)
        visited[num] = True

        for i in range(N, 0, -1):
            if edges[num][i] and not visited[i]:
                stack.append(i)
    return answer

def BFS(N, edges, V):
    visited = [False]*(N+1)    
    que = deque([V])
    visited[V] = True
    answer = [V]

    while que:
        num = que.popleft()
        for i in range(1, N+1):
            if edges[num][i] and not visited[i]:
                visited[i] = True
                answer.append(i)
                que.append(i)
    return answer


N, M, V = map(int,input().split())
edges = [[False] * (N+1) for i in range(N+1)]
for i in range(M):
    a, b = map(int,input().split())
    edges[a][b] = True
    edges[b][a] = True

print(*DFS(N, edges, V))
print(*BFS(N, edges, V))

224ms