[백준(BOJ) / Python] 1260번: DFS와 BFS

문제 링크: www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

문제 설명

단순히 DFS와 BFS를 수행하면 됩니다.

저는 (N + 1) X (N + 1) 크기의 matrix를 이용해 정점 간의 간선을 표시했습니다.

또한 dfs를 할 땐 방문한 노드를 1로 표현하고 bfs를 할 땐 0으로 표현해서 visited를 따로 초기화할 필요 없이 바로 사용할 수 있도록 했습니다. 

 

 

 

소스코드

def dfs(v):
    # 방문 노드 1로 표현
    visited[v] = 1
    print(v, end = ' ')
    for i in range(1, n + 1):
        # 인접 노드 중 방문하지 않은 노드 탐색
        if visited[i] == 0 and matrix[v][i] == 1:
            dfs(i)

def bfs(start):
    queue = [start]
    # 방문 노드 0으로 표현
    visited[start] = 0

    while queue:
        v = queue.pop(0)
        print(v, end = ' ')
        for i in range(1, n + 1):
            # 인접 노드 중 방문하지 않은 노드 방문
            if visited[i] == 1 and matrix[v][i] == 1:
                queue.append(i)
                visited[i] = 0

n, m, v = map(int, input().split())
visited = [0] * (n + 1)
# matrix에 연결된 노드 표시
matrix = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    i, j = map(int, input().split())
    matrix[i][j] = 1
    matrix[j][i] = 1

dfs(v)
print()
bfs(v)