[ BOJ 1260 ] DFS와 BFS(Python)

문제

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

똑같이 주어지는 정점에 대해서 dfs,bfs 값을 구하면 된다.
방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문 해야 한다는 점 ...만 주의하면 된다. 🙂

문제 풀이

0. 우선 주어진 간선을 양방향으로 연결해준다.
1. dfs
   1-1. 시작점을 stack 리스트에 추가해준다.
   1-2. 가장 앞에 있는 요소를 pop 해서 node 변수에 넣어준다.
   1-3. node를 방문 안했을때, 방문 체크를 해준 뒤 node와 연결된 다른 정점들 중 방문 안한 정점들만 temp 리스트에 넣어준다.
   1-4. temp를 내림차순으로 정렬해준다.
   (stack에서 pop을 할 때 가장 앞에 있는 요소를 빼니까)
   1-5. stack에 temp를 추가해준다.
   1-6. stack에서 연결된 요소를 모두 확인했으면 출력하기
2. bfs
   2-1. 시작점을 queue에 추가해준다.
   2-2. 가장 앞에 있는 요소를 popleft해서 node 변수에 넣어준다.
   2-3. node를 방문 안했을때,방문체크를 해준 뒤 node와 연결된 다른 정점들 중 방문 안한 정점들만 temp 리스트에 넣어준다.
   2-4. temp를 오름차순으로 정렬해준다.
   2-5. queue에 temp를 추가해준다.
   2-6. queue에서 연결된 요소를 모두 확인했으면 출력하기

코드

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

#정점 개수 n, 간선 개수 m, 탐색을 시작할 정점 번호 v
n, m, v = map(int,(input().rstrip().rsplit()))
nodes = []
graph = {}


def dfs(graph, start_node):
    visit = []
    stack = []
    
    stack.append(start_node)
    while stack:
        #가장 뒤에 있는 요소 pop
        node = stack.pop()
        if node not in visit:
            visit.append(node)
            if node in graph:
                temp = list(set(graph[node])-set(visit))
                temp.sort(reverse=True)
                stack += temp
    return " ".join(str(i) for i in visit)

def bfs(graph, start_node):
    visit = []
    queue = deque()

    queue.append(start_node)
    while queue:
        #가장 앞에 있는 요소 pop
        node = queue.popleft()
        if node not in visit:
            visit.append(node)
            if node in graph:
                temp = list(set(graph[node])-set(visit))
                temp.sort()
                queue += temp
    return " ".join(str(i) for i in visit)

for i in range(m):
    x,y = map(int,input().rstrip().rsplit())
    nodes.append([x,y])

    if x not in graph:
        graph[x]=[y]
    else:
        graph[x].append(y)

    if y not in graph:
        graph[y]=[x]
    else:
        graph[y].append(x)

print(dfs(graph,v))
print(bfs(graph,v))