기본 DFS와 BFS

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

1260번: DFS와 BFS

해당 문제는 간단해 보였지만 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문 하라는 조건 때문에 응근히 까다롭게 느껴졌다.

 

n, m, v = map(int, input().split())
graph1 = {}
visited = list()
visited_dfs = list()
need_visited = list()
need_visited.append(v)
need_visited_dfs = list()
need_visited_dfs.append(v)

for _ in range(m):
    key, value = map(int, input().split())
    if key in graph1:
        graph1[key].append(value)
    else:
        graph1[key] = [value]

while need_visited:
    vertex = need_visited.pop(0)
    if vertex not in visited:
        visited.append(vertex)
        if vertex in graph1:
            need_visited.extend(graph1[vertex])

while need_visited_dfs:
    vertex = need_visited_dfs.pop()
    if vertex not in visited_dfs:
        visited_dfs.append(vertex)
        if vertex in graph1:
            need_visited_dfs.extend(graph1[vertex])
print(visited)
print(visited_dfs)

위 코드가 처음에 작성한 코드였다. 정점 번호가 작은걸 우선 방문하라는 조건을 빼면 일반 DFS, BFS 기능은 나온 것 같다. 작은걸 우선 방문하라는 조건을 지키기 위해서는 DFS와 BFS의 정렬 순서가 역정렬이 되어야 조건을 충족시킬 수 있을 것으로 보인다. 

아래 코드가 답코드이다.

from collections import deque

def dfs(v):
    print(v, end= ' ')
    visited[v] = True
    for e in adj[v]:
        if not(visited[e]):
            dfs(e)
def bfs(v):
    q = deque([v])
    while q:
        v = q.popleft()
        if not(visited[v]):
            visited[v] = True
            print(v, end=' ')
            for e in adj[v]:
                if not visited[e]:
                    q.append(e)
    
n, m, v = map(int, input().split())
adj = [[] for _ in range(n+1)]

for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)
for e in adj:
    e.sort()
    
visited = [False] * (n + 1)
dfs(v)
print()
visited = [False] * (n + 1)
bfs(v)

deque를 사용하는 이유는 그냥 list를 사용하는거 보다 성능상 유리한 면이 있어서인 것 같다.