[알고리즘] 백준 1260 DFS와 BFS - 파이썬

어제 공부했던 DFS, BFS문제를 이어 풀어보았습니다. 백준 단계별 풀기에서 'BFS, DFS' 문제가 11문제 정도되는데 학기중이니 하루에 한문제씩이라도 꾸준히 풀생각입니다.

 

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

1260번: DFS와 BFS

 

from collections import deque
from sys import stdin

n, m, v = map(int, stdin.readline().split())
graph = [[0] * (n+1) for _ in range(n+1)] # 인접행렬

for _ in range(m):
    x, y = map(int, stdin.readline().split())
    graph[x][y] = 1
    graph[y][x] = 1

visited = [False] * (n + 1)  # 방문노드 False로 초기화

def dfs(graph, v):

    visited[v] = True # 방문하면 True
    print(v, end=' ') # 방문한 노드 출력
    for i in range(len(graph[v])):
        if graph[v][i] == 1 and visited[i] == False:
            dfs(graph, i)


def bfs(graph, v):
    queue = deque([v])
    visited = [False] * (n + 1)  # 방문노드 False로 초기화
    visited[v] = True

    while queue:
        v = queue.popleft() # 방문한 노드 pop
        print(v, end=' ') # 방문한 노드 출력
        for i in range(len(graph[v])):
            if graph[v][i] == 1 and visited[i] == False:
                queue.append(i) # 순서대로 담기
                visited[i] = True # 담는 즉시 방문기록

dfs(graph, v)
print()
bfs(graph, v)

 

 

문제풀이 : 처음에는 바로 전에 문제 풀듯이 각 노드만다 인접한 노드를 배열에 담아 풀어보려했지만 이번 문제는  두 정점의 번호를 입력으로 받습니다. 인접행렬을 통해서 문제를 해결해야한다는 점만 다른 블로그를 참고하여 마저 풀어보았습니다. 역시나 이번 문제도 dfs는 재귀, bfs는 deque를 활용해서 풀 수 있었던 문제였습니다.