Coordinates

• (u,v) 를 연결하는 엣지가 있을때, 둘 중 한 노드의 좌표를 알고 있으면 다른쪽 노드의 좌표도 계산이 가능하다.
• 처음에 노드 하나를 임의의 좌표로 지정하고 (첫 좌표를 (0,0)으로 잡으면 모든 좌표들이 범위 안에 들어간다), 그 노드에 연결된 노드들에 대해서 좌표를 계산하고 다시 여기에 연결된 노드에 대해서 좌표를 계산하고 하는 식으로, BFS나 DFS로 그래프를 탐색해나가면서 방문된 노드들의 좌표를 갱신해주면 끝. 시간복잡도는 O(N+M)
• 이렇게 놓고 보면 단순한 BFS/DFS 문제이지만, 파이썬 기준으로는 시간이 좀 빡빡하다. N은 최대 100,000으로 크지 않은데, M이 최대 1,000,000 이다. 최적화를 따로 하지 않기는 했지만, python3.11으로는 시간초과가 났고, Pypy로 약 4000ms에 통과되었다.
• 코드 하나하나 최적화를 하는것 보다도 BFS에 들어가는 그래프의 크기를 줄이도록 변경했다. 모든 노드가 연결되어있기만 하면 좌표 계산이 가능하므로, 불필요한 엣지들을 제거해서 트리형태로 만들고 거기에서 DFS/BFS를 돌려도 모든 노드의 좌표를 구할수 있다. disjoint set을 이용해서 먼저 그래프를 트리로 변형한 다음에 DFS를 돌렸더니 pypy로는 약 1900ms, python 3.11에서는 2616ms 에 돌아갔다.
  • 시간복잡도 자체는 dsu 전처리가 O(M*α(N)), BFS가 O(N)으로 그냥 bfs를 하는것과 별 차이는 없다

"""Solution code for "BOJ 13899. Coordinates".

- Problem link: https://www.acmicpc.net/problem/13899
- Solution link: http://www.teferi.net/ps/problems/boj/13899

Tags: [graph]
"""

import sys
from teflib import tree as ttree
from teflib import disjointset


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    graph = [[] for _ in range(N)]
    coord_diff = [{} for _ in range(N)]
    dsu = disjointset.DisjointSet(N)
    for _ in range(M):
        a, b, dx, dy = [int(x) for x in sys.stdin.readline().split()]
        if dsu.union_if_disjoint(a - 1, b - 1):
            graph[a - 1].append(b - 1)
            graph[b - 1].append(a - 1)
            coord_diff[a - 1][b - 1] = (dx, dy)
            coord_diff[b - 1][a - 1] = (-dx, -dy)

    source = 0
    coords = [None] * N
    coords[source] = (0, 0)
    for u, p in ttree.dfs(graph, source):
        if u != source:
            px, py = coords[p]
            dx, dy = coord_diff[p][u]
            coords[u] = px + dx, py + dy

    for x, y in coords:
        print(x, y)


if __name__ == '__main__':
    main()

• Dependency.
  • teflib.disjointset.DisjointSet
  • teflib.tree.dfs