백준-1260번 DFS와 BFS (extendleft)

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

1260번: DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

풀이

생각보다 오래걸린 문제이다. 단순히 DFS와 BFS만 구현할 것이 아니라, 방문할 수 있는 정점이 여러개인 경우에는 정점 번호가 작은 것부터 방문해야 하므로 노드에 연결된 다른 노드들을 정렬해야 한다!

 

또한, deque의 extendleft 사용시에 값들이 반대로 들어가므로 리스트를 뒤집어줘야 원하는 순서대로 들어간다!

 

extendleft 예시

3, 4, 5 앞에 1, 2를 넣고 싶을 경우

 

그냥 extendleft를 사용하면 아래처럼 순서가 반대로 들어감!

a = deque([3, 4, 5])
a.extendleft([1, 2])
print(a)
// deque([2, 1, 3, 4, 5])

넣으려고 하는 리스트를 한번 뒤집어줘야함!

a = deque([3, 4, 5])
a.extendleft(reversed([1, 2]))
print(a)
// deque([1, 2, 3, 4, 5])

답

import sys

from collections import deque

N, M, V = map(int, sys.stdin.readline().split())

graph = dict()
a = deque()
for i in range(M):
    x, y = map(int, sys.stdin.readline().split())
    if x not in graph.keys():
        graph[x] = list()
    if y not in graph.keys():
        graph[y] = list()
    graph[x].append(y)
    graph[y].append(x)


for i in graph.keys():
    graph[i].sort()


def dfs(graph_):
    visited = deque()
    need_visit = deque()
    need_visit.append(V)

    if V not in graph.keys():
        print(V)
        return

    while need_visit:
        node = need_visit.popleft()
        if node not in visited:
            visited.append(node)
            need_visit.extendleft(reversed(graph_[node]))
    for n in visited:
        print(n, end=' ')
    print()


def bfs(graph_):
    visited = deque()
    need_visit = deque()
    need_visit.append(V)

    if V not in graph.keys():
        print(V)
        return

    while need_visit:
        node = need_visit.popleft()
        if node not in visited:
            visited.append(node)
            need_visit.extend((graph_[node]))
    for n in visited:
        print(n, end=' ')

dfs(graph)
bfs(graph)