[백준 1260번] DFS와 BFS

🎯 백준 - 1260. DFS와 BFS

---

🤔 나의 풀이

📌 문제

- 백준 1260번 DFS와 BFS
- DFS와 BFS 기본 활용 문제

📌 날짜

2021.02.11

📌 시도 횟수

6 try

💡 Code

from collections import defaultdict
from collections import deque

# DFS
def dfs(i):
    traced.add(i)
    print(i, end=" ")

    for x in graph[i]:
        if x not in traced:
            dfs(x)
    return


# BFS
def bfs(i):
    traced.add(i)
    queue = deque([i])
    print(i, end=" ")

    while queue:
        v = queue.popleft()
        for w in graph[v]:
            if w not in traced:
                traced.add(w)
                queue.append(w)
                print(w, end=" ")


# graph 생성
N, M, V = map(int, (input().split()))
graph = defaultdict(list)

for _ in range(M):
    start, end = map(int, (input().split()))
    graph[start].append(end)  # 양방향 그래프로 생성
    graph[end].append(start)

for key in list(graph):
    graph[key].sort()  # 정점 번호가 작은 것을 먼저 방문

# 실행
traced = set()
dfs(V)
print()
traced = set()
bfs(V)

💡 문제 해결 방법

- dfs, bfs의 기본적인 틀을 활용했다.
- 단, 문제에서 간선은 양방향이라고 했으므로 그래프를 생성할 때 양방향으로 만들었다.
- 정점 번호가 작은 것을 먼저 방문해야 되므로 value를 sort했다.

💡 새롭게 알게 된 점

- 양방향 그래프 만드는 방법
>> key ↔ value를 서로 바꾼 것을 한번 더 dict에 추가해주면 된다.
>>    graph[start].append(end)
>>    graph[end].append(start)

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 양방향 그래프라는 조건을 제대로 고려하지 않아 계속 오류가 떴다😾