백준 1260 문제 분석 python

🐒 DFS와 BFS

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

✍ 나의 풀이

import sys
from collections import deque



n, m, v = map(int, input().split())


graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, n+1):
    graph[i].sort()

def dfs(x):
    visited[x] = True
    print(x , end=' ')
    for i in graph[x]:
        if not visited[i]:
            dfs(i)

def bfs(x):
    visited[x] = True
    queue = deque([x])
    while queue:
        x = queue.popleft()
        print(x, end=' ')
        for i in graph[x]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

dfs(v)
visited = [False] * (n+1)
print()
bfs(v)

참고한 풀이

---

🧠 문제 이해

DFS 와 BFS 알고리즘 사용법을 익힐수있는 문제였다.

아직도 헷갈리지만 코드를 한줄씩 따라적으니 조금씩 이해가 되더라.

두번째 예제에서

5 5 3
5 4
5 2
1 2
3 4
3 1

입력을 이렇게 했을때
나의 풀이로 나온 출력은

3 4 5 2 1 
3 4 1 5 2

이었고, 오답이었다.
답은

3 1 2 5 4
3 1 4 2 5

이었다.

나의 풀이와 답이 다른 이유는

for i in range(1, n+1):
	graph[i].sort()

위 코드로 각 노드를 올림차순으로 정렬하지 않았기 때문인데,

순서가 없는 양방향 노드라면서 답이 여러개여야 하는거 아닌가 하면서 삽질을 하다가 문제에
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,
라는 구절을 뒤늦게 보고나서 납득했다.😇

---

세상엔 똑똑한 사람들이 많구나