2023.01.16 백준 DFS와 BFS

 

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

1260번: DFS와 BFS

import sys
from collections import defaultdict
from collections import deque

input = sys.stdin.readline

def dfs(start,visited = []):
    visited.append(start) 
    print(start,end=' ')
    for i in graph_dic[start]:
        if i not in visited:
            dfs(i,visited)

def bfs(starts):
    visited_bfs = []
    discovered = deque([starts])
    while discovered:
        visit = discovered.popleft()
        visited_bfs.append(visit)
        print(visit,end=' ')
        for i in graph_dic[visit]:
            if i in visited_bfs or i in discovered:
                continue
            discovered.append(i)
    return visited_bfs

N ,M, V= map(int,input().split()) # n은 정점의 개수 n 간선의 개수 v 시작할 노드
graph = [list(map(int,input().split())) for _ in range(M)]
graph_dic = defaultdict(list)

#print(graph)

graph = sorted(graph,key = lambda x: (min(x[0],x[1]),max(x[0],x[1])))

for i in graph:
    graph_dic[i[0]].append(i[1])
    graph_dic[i[1]].append(i[0])

#print(graph_dic)
# defaultdict(<class 'list'>, {1: [2, 3], 2: [1, 5], 3: [1, 4], 4: [3, 5], 5: [2, 4]})
dfs(V)
print()
bfs(V)

 

단순하게 DFS랑 BFS 구현하는 문제였는데 틀렸다고 많이 떠서 그거 찾는다고 2일정도 써버렸다.

계속 틀렸던 이유는 sorted 부분에서 전에는 그냥 x[0] 을 기준으로 정렬을 했었는데 3,1 같은 거를 생각 못하고 넘겨버렸다가 bfs dfs 부분에 문제 있는 줄 알고 엄한곳에 삽질을 하고 있었다.