[백준] 1260 - DFS와 BFS (python 파이썬)

백준 1260 문제 바로가기

문제 사진이 조금 짤린 점 양해바랍니다!

풀이 코드

from collections import deque

n, m, v = map(int, input().split())  # n은 정점, m은 간선의 수, v는 시작 번호
graph = [[] for _ in range(n + 1)]
dfs_visited = [0] * (n + 1)
bfs_visited = [0] * (n + 1)
dfs_result = []
bfs_result = []

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


def dfs(start):
    print(start, end=' ')
    dfs_visited[start] = 1
    dfs_result.append(start)

    for i in graph[start]:
        if dfs_visited[i] == 0:
            dfs(i)


def bfs(start):
    bfs_visited[start] = 1
    q = deque()
    q.append(start)

    while q:
        d = q.popleft()
        print(d, end=' ')
        bfs_result.append(d)
        for i in graph[d]:
            if bfs_visited[i] == 0:
                q.append(i)
                bfs_visited[i] = 1


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

dfs(v)
print()
bfs(v)

DFS, BFS를 둘 다 적용시켜서 결과를 도출해내야하는 문제다! 뭔가 기본적인 정석같은 느낌?,,이었다.
다만, 좀 삽질했던 부분은 방문할 수 있는 부분이 여러개면 작은 노드부터 방문한다고 문제에 있었는데...그걸 못봐서 시간을 썼다 ,,,
보자마자 아차 싶어서 sort로 정렬시키고 dfs, bfs를 통해 결과 도출 성공!

회고

문제를 꼼꼼하게 읽자!