백준 16940번 BFS

서론

16940번: BFS 스페셜 저지

BFS, DFS 관련 문제를 풀다가 재밌는 문제를 만나서 적습니다. BFS, DFS 문제는 이제 어느 정도 풀게 되었는데 이문제에서는 BFS를 거꾸로 구성한다는 느낌을 받아서 새로웠습니다. 요점은 BFS로 그래프 탐색 시 인접노드에 순서를 주지 않으면 여러 개의 탐색경로가 나올 수 있고 주어진 답이 그 탐색경로 중 한 개인지를 확인하는 것입니다.

처음에는 모든 탐색 경로를 구해서 주어진 경로가 알맞은지 확인했는데 답은 맞은 것 같았지만 당연히 시간초과가 났습니다. 꽤 오랜 시간 생각을 했지만 생각이 안 나서 결국 다른 사람 코드를 보고 도움을 받았고 큰 감명을 받았습니다.

저는 계속해서 그냥 풀던 대로 주어진 그래프를 가지고 BFS를 탐색하며 경로를 찾겠다는 생각만 했는데 문제에서 요구한 건 확인해야 하는 경로를 가지고 그래프를 재구성해서 그걸로 BFS 한 번만 돌리는 거였습니다.

제한 조건

BFS, DFS 문제들은 제한을 심하게 두진 않기 크게 신경 쓰지 않아도 된다고 생각합니다. 그래도 최적화를 위해서 탐색해야 하는 graph나 map은 한 번만 훑는 것이 좋고 또 함수를 사용한다면 함수 내에 인자로 전달해서 괜히 복사하여 시간과 메모리를 잡아먹지 말고 그냥 전역변수로 사용하는 것이 좋습니다.

• 시간제한 - 2초

시간제한은 2초입니다. 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준을 가지고 풉니다. 그래프를 만드는 함수나, 정렬하는 함수, 그리고 BFS 함수에서도 병목구간이 딱히 없고 모두 최대 vertex 수 100,000을 기준으로 동작하니 시간복잡도는 O(n)이라고 볼 수 있습니다.

• 메모리 제한 - 512MB

메모리 제한은 512MB입니다. 코드에서 크게 메모리를 잡아먹는 부분이 그래프인데 애초에 그래프의 크기가 vertex 100,000을 기준으로 하므로 커봐야 100KB 이상이고 edge 정보 100,000개를 담아도 200KB 그리고 visited나 path 리스트를 담더라도 400KB 정도니 메모리는 충분합니다.

BFS

위에서 말했던 것처럼 주어진 그래프를 가지고 BFS 경로를 탐색하며 주어진 조건과 비교하면 시간초과가 나오고 주어진 BFS를 경로를 가지고 graph를 정렬하여 한 번만 BFS를 실행하여야 합니다. 그리고 그 두 개가 일치하면 주어진 BFS 경로가 가능한 경로입니다.

이 개념을 이해하는데 꽤 오랜 시간이 걸렸는데 역시 이해하고 보니까 그렇게 또 엄청난 건 아닌 것 같습니다. 아래가 주어진 경로를 보고 그래프의 인접노드 순서를 정렬하는 코드인데, 기본적으로 주어진 경로에서 먼저 등장한 노드들이 인접노드로도 더 빠른 순서로 들어간다는 개념입니다. 개념을 이해한 후로는 order 리스트나 sort 함수의 활용 정도만 눈여겨 보면 될 것 같습니다.

def make_ordered_graph(graph, solution):
    ordered_graph = graph.copy()
    order = [0] * (vertex_num+1)

    for i in range(len(solution)):
        order[solution[i]] = i
    for i in range(1, len(graph)+1):
        ordered_graph[i].sort(key=lambda x: order[x])

    return ordered_graph

전체 코드는 아래와 같습니다.

import sys
from collections import deque as dq
input = sys.stdin.readline

vertex_num = int(input())
edge_list = [list(map(int, input().split())) for __ in range(vertex_num-1)]
solution = list(map(int, input().split()))


def make_graph(vertex_num, edge_list):
    graph = {}
    for i in range(1, vertex_num+1):
        graph[i] = []
    for edge in edge_list:
        node1, node2 = edge
        graph[node1].append(node2)
        graph[node2].append(node1)

    return graph


def make_ordered_graph(graph, solution):
    ordered_graph = graph.copy()
    order = [0] * (vertex_num+1)

    for i in range(len(solution)):
        order[solution[i]] = i
    for i in range(1, len(graph)+1):
        ordered_graph[i].sort(key=lambda x: order[x])

    return ordered_graph


def BFS(graph):
    que = dq()
    visited = [0] * (vertex_num+1)

    que.append(1)
    visited[1] = 1
    path = [1]

    while que:
        basev = que.popleft()
        for nextv in graph[basev]:
            if visited[nextv] == 0:
                que.append(nextv)
                visited[nextv] = 1
                path.append(nextv)

    return path


graph = make_graph(vertex_num, edge_list)
ordered_graph = make_ordered_graph(graph, solution)
path = BFS(ordered_graph)

if path == solution:
    print(1)
else:
    print(0)

생각

BFS, DFS 개념을 굉장히 잘 잡았다고 생각했는데 이런 새로운 문제가 나오니까 또 접근하기가 너무 힘든 것 같습니다. 문제를 많이 풀면 나아질 거라고 생각하고 계속 풀어보겠습니다.

이번에는 코드 구조(파이썬 표준 코딩 스타일 가이드 PEP 8)에 대해서 한번 생각을 한 후라서 코드를 조금 예쁘게 짜보려고 노력했습니다. 변수명도 정성스럽게 지었고, 함수나 함수를 부르는 흐름 자체도 더 이해하기 쉽게 만들려고 노력했습니다. 근데 뭔가 오히려 코드가 길어져서 이게 맞는 건진 모르겠습니다. 그리고 가독성을 위해서 인풋데이터를 리스트에 한 번 저장해놓고 그걸로 다시 그래프를 만드는 방법 같은 건 메모리 측면에서는 최적화도 되지 않은 방법인데, 오로지 가독성만을 위해서 이렇게 코딩하는 게 맞는 건지는 잘 모르겠습니다. 앞으로도 다른 사람 코드를 많이 보면서 배워야겠습니다.