[til][bj1260]dfsbfs

21 Jan 2025

Type : DFS, BFS Basic
Key : 무지성으로 자료구조를 만들면 안되는 이유(모르겠으면 반례를 검색하자)

Insight

이문제는 예전에 풀었던 것이었는데, 계속 runtime error가 나왔다.
확인해보니, 시작하는 간선이 없을 경우 dictionary는 key를 못찾아서 error를 낸다는 것이었다.
- https://www.acmicpc.net/board/view/37362

이전에 풀었을때는 자료 구조를 N개의 list를 일단 생성하고 보자는 것이기에, 자료 공간이 있으니 error가 안났었다.

```
graph = [[] for _ in range(N+1)]
```

현재

graph = {}
graph[V] = [] #KEY
for idx in range(M):
    A,B = map(int ,input().split())
    if A not in graph:
        graph[A] = [B]
    else:
        graph[A].append(B)
    if B not in graph:
        graph[B] = [A]
    else:
        graph[B].append(A)
    
for _ in graph:
    graph[_].sort()

이 문제를 통해 두 가지 Insight를 얻었다.
1. C++로 짠다면 나는 속도측면에서 unorded_map을 썼겠지, 그때도 dict과 동일한 이유를 잘 생각해놓자
2. 에러가나면 반례를 검색해서, 코드 헤메는 시간을 줄이자

Code

import sys
sys.stdin = open('sample.txt')

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

graph = {}
graph[V] = [] # Key

for idx in range(M):
    A,B = map(int ,input().split())
    if A not in graph:
        graph[A] = [B]
    else:
        graph[A].append(B)
    if B not in graph:
        graph[B] = [A]
    else:
        graph[B].append(A)

for _ in graph:
    graph[_].sort()


# DFS
visited_for_dfs = [ 0 for _ in range(N+1)]
def dfs(start):
    visited_for_dfs[start] = 1
    print(start, end=" ")
    for next_ in graph[start]:
        if visited_for_dfs[next_] != 0:
            continue
        dfs(next_)

# BFS
from collections import deque

def bfs(start):
    queue = deque()
    queue.append(start)
    visited = [ 0 for _ in range(N+1) ]
    visited[start] = 1

    while queue:
        cur = queue.popleft()
        print(cur, end=" ")
        for next_ in graph[cur]:
            if visited[next_] != 0:
                continue
            visited[next_] = 1
            queue.append(next_)

dfs(V)
print()
bfs(V)