백준 문제 풀이 - DFS와 BFS 1260번

📜 문제 이해하기

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

💡 문제 재정의

그래프에서 dfs와 bfs 결과를 출력하자.

✏️ 계획 수립

먼저 그래프를 표현하기 위해 쓸 수 있는 방법은 인접 행렬과 인접 그래프가 존재한다. 이 문제에선 정점의 개수가 최대 1000개이고 간선의 개수가 최대 10000개이기에 인접 행렬을 쓰는것이 조금 더 효율적이기 때문에 인접 행렬로 구현한다.
1) dfs
dfs는 각 노드마다 재귀호출을 하면 쉽게 구현할 수 있다.
연결된 노드마다 dfs를 호출해주면 된다.
2) bfs
두개의 반복문으로 구현할 수 있다. 갈 수 있는 노드들을 저장하는 큐를 만들고 큐에서 순서대로 pop하면서 노드들을 방문한다.

💻 계획 수행

# 엣지의 개수가 노드의 개수보다 많기 때문에 인접 행렬로 구현
import sys


def dfs(current_node, _adjacent_matrix, _node_state):
    print(current_node, end=' ')
    _node_state[current_node] = 'V'
    for node, connected in enumerate(_adjacent_matrix[current_node]):
        if connected and _node_state[node] == 'U':
            dfs(node, _adjacent_matrix, _node_state)
    _node_state[current_node] = 'F'


def bfs(start_node, _adjacent_matrix, _node_state):
    _node_state[start_node] = 'V'
    possible_node = [start_node]
    while possible_node:
        current_node = possible_node.pop(0)
        print(current_node, end=' ')
        for node, connected in enumerate(_adjacent_matrix[current_node]):
            if connected and _node_state[node] == 'U':
                possible_node.append(node)
                _node_state[node] = 'V'


if __name__ == '__main__':
    V, E, first_node = map(int, sys.stdin.readline().split())
    # 0번은 안쓰는 인덱스, 1번부터 시작
    adjacent_matrix = [[0] * (V + 1) for i in range(V + 1)]
    node_state = ['U' for i in range(V + 1)]

    for _ in range(E):
        node1, node2 = map(int, sys.stdin.readline().split())
        adjacent_matrix[node1][node2] = 1
        adjacent_matrix[node2][node1] = 1

    dfs(first_node, adjacent_matrix, node_state)
    print()
    node_state = ['U' for i in range(V + 1)]
    bfs(first_node, adjacent_matrix, node_state)

🤔 회고

오랜만에 그래프 문제를 풀었다. 항상 풀고나면 별게 아닌것같지만 처음에 생각하는게 어려운 것 같다.