1260번 파이썬

bfs랑 dfs를 공부했던 블로그를 참고해서 했는데 정점과 간선을 이용한 그래프를 python의 dictionary를 이용하면 편리하게 정점 사이의 연결들을 관리할 수 있는 것 같다.

dfs의 경우 stack의 pop과 정렬할 때 reverse 옵션을 true로  했는데 dfs가 깊이 탐색이다 보니

처음에 시작점으로 주어진 v에서 뻗쳐나갈 때 하나의 깊은 가지까지 다 뻗어나가고 나서야 다른 가지를 탐색하기 때문이다. 예를 들어

처음 입출력을 예로 들어

연결된 간선을 dic으로 표현하면 {1:[2,3,4],2:[1,4],3:[1,4],4:[1,2,3]}가 되는데

1번을 시작점으로 잡았을 경우 1(stack 배열이 reverse를 만나면서 [4,3,2]로 바뀜)->2( stack에서 2를 꺼내고 2랑 연결된 4를 집어넣음 stack=[4,3,2,4])  ->4(4를 꺼내고 4랑 연결된 1,2,3중 방문 안한 3만 넣음 stack=[4,3,2,3]) -> 3(3을 꺼내고 3이랑 연결된 정점들은 모두 방문했으므로 stack=[4,3,2]가 되고 이후 stack의 pop만 반복하다 종료)

만약 sort할때 역순으로 안했다면 stack은 LIFO구조이기 때문에  주어진 문제의 조건인 "정점이 여러 개인 경우, 정점 번호가 작은 거부터 먼저 방문"이 불가능하게 된다.

BFS의 경우에는 collections 모듈에 있는 deque 자료구조를 이용했다. deque는 FIFO인 queue와 달리 앞뒤에서 추가 삭제가 가능한 자료구조이다. 따라서 bfs는 넓이 우선 탐색이다 보니 자료를 정렬해서 앞에서부터 빼주면 문제의 조건을 만족할 수 있다.

참고로 파이썬은 그냥 input을 할때 시간이 오래걸리니 꼭 sys에 있는 readline을 이용!!

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

def dfs(graph,r):
    stack=[r]
    visited=[]
    while 1:
        if not len(stack):
            break
        item=stack.pop()
        if item not in visited:
            visited.append(item)
            if item in graph:
                ary=list(set(graph[item])-set(visited))
                ary.sort(reverse=True)
                stack+=ary
    return ' '.join(str(i) for i in visited)
                
def bfs(graph,r):
    visited=[]
    queue=deque([r])
    while 1:
        if not len(queue):
            break
        item = queue.popleft()
        if item not in visited:
            visited.append(item)
            if item in graph:
                ary=list(set(graph[item])-set(visited))
                ary.sort()
                queue+=ary
                
    return ' '.join(str(i) for i in visited)
n,m,v= map(int,input().split())
graph = {}
for _ in range(m):
    num1,num2=map(int,input().split())
    if num1 not in graph:
        graph[num1]=[num2]
    elif num2 not in graph[num1]:
        graph[num1].append(num2)
    if num2 not in graph:
        graph[num2]=[num1]
    elif num1 not in graph[num2]:
        graph[num2].append(num1)
        
print(dfs(graph,v))
print(bfs(graph,v))