BOJ1260 DFS와 BFS

문제

BOJ1260 DFS와 BFS
실버II | 백준 1260 | Python3 파이썬 풀이

알고리즘

기본적인 BFS, DFS 문제이지만, 이 문제의 포인트는 자식 노드를 방문할 때, 값이 더 작은 노드를 우선 방문해야 한다는 조건이 추가되었다. (그냥 그래프 탐색을 할 때는 대부분 신경쓰지 않는다)

인접행렬을 구성할 때 작은 값이 오므로 BFS의 경우는 상관이 없지만, DFS는 스택을 사용하므로 값 순서가 바뀌게 된다. 그래서 임시 리스트를 생성하고 반대로 담아주었다.

코드

import sys
from collections import deque

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

adj = [[False for j in range(N)] for i in range(N)]
visited = [False for i in range(N)]

for i in range(M):
    x, y = map(int, sys.stdin.readline().split())
    adj[x - 1][y - 1] = True
    adj[y - 1][x - 1] = True

# // DFS
curr = V - 1
stack = deque()
stack.append(curr)

while(len(stack) != 0):
    curr = stack.pop()
    
    if not visited[curr]:
        visited[curr] = True
        sys.stdout.write(str(curr + 1) + ' ')

        temp = list()
        for n in range(N):
            if adj[curr][n] and not visited[n]:
                temp.append(n)

        temp.reverse()
        for t in temp:
            stack.append(t)

sys.stdout.write('\n')

# // BFS
visited = [False for i in range(N)]

curr = V - 1
queue = deque()
queue.append(curr)
visited[curr] = True

while(len(queue) != 0):
    curr = queue.popleft()
    sys.stdout.write(str(curr + 1) + ' ')

    temp = list()
    for n in range(N):
        if adj[curr][n] and not visited[n]:
            queue.append(n)
            visited[n] = True

결과