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

문제 (링크)

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

1260번: DFS와 BFS

 

나의 풀이

from collections import deque
n, m, v = map(int, input().split())

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

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

def bfs(v):
    queue = deque([v])
    visited[v] = True
    
    while queue:
        x = queue.popleft()
        print(x, end=' ')
        
        for i in range(len(matrix[x])):
            if matrix[x][i] == 1 and visited[i] == False:
                queue.append(i)
                visited[i] = True
                
    
def dfs(v):
    visited[v] = True
    print(v, end=' ')
    
    for i in range(len(matrix[v])):
        if visited[i] == False and matrix[v][i] == 1:
            dfs(i)

dfs(v)
visited = [False] * (n+1) # DFS를 한 번 실행하고 나면 visited가 모두 True로 바뀌기 때문에 수정해줌
print()
bfs(v)

 

일반적인 bfs와 dfs를 구현하는 방식을 이용했다.

 

하지만, 내가 지금까지 풀어본 방식은 인접여부를 0과 1로 지정하는 것이 아니라 직접 노드의 번호를 입력하는 방식이었기 때문에 코드를 작성하는데 어려움이 있었다.

 

알고리즘 공부할 때마다 막혔던 부분이 이 DFS / BFS 부분인데, 기초적이긴 해도 이걸 풀었다는게 너무 감격스럽다.

 

조금 더 힘내서 공부할 수 있을 것 같다.