[DFS, BFS] 백준 1260번 DFS와 BFS with Python3

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

1260번: DFS와 BFS

문제

내 풀이

from collections import deque


def bfs(start):
    que = deque([start])
    visit_list[start] = 1
    while que:
        vv = que.popleft()
        print(vv, end=' ')
        for i in range(1, n+1):
            if visit_list[i] == 0 and graph[vv][i] == 1:
                que.append(i)
                visit_list[i] = 1


def dfs(v):
    visit_list2[v] = 1
    print(v, end=" ")
    for i in range(1, n + 1):
        if visit_list2[i] == 0 and graph[v][i] == 1:
            # 1. 방문한 적이 없고,
            # 2. 현재 v 노드에서 i노드로 간선이 연결되어있다면
            dfs(i)


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

graph = [[0] * (n + 1) for _ in range(n + 1)]
visit_list = [0] * (n + 1)
visit_list2 = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1

dfs(v)
print()
bfs(v)

해설

기초적인 dfs와 bfs 구현 문제 였다.

동빈나 강의 영상을 참고하여 구현했다.

가장 어려웠던 부분은 주어지는 입력값이 강의에서 나오던 예시와 달랐다는 점이다. 

결국 2차원 맵핑으로 x 1에 y 2 에 1의 값이 있다면 노드 1에서 2로 갈 수 있다 라는 식으로 정리했다. vice versa.

 

이러한 요소들이 문제의 난이도를 키우는 부분이 아닐까 짐작하게 됐다.