사용자 도구

사이트 도구


ps:problems:boj:10775

공항

ps
링크acmicpc.net/…
출처BOJ
문제 번호10775
문제명공항
레벨골드 2
분류

Disjoint Set

시간복잡도O(m+n*α(m))
인풋사이즈n<=10^5, m<=10^5
사용한 언어Python
제출기록39356KB / 288ms
최고기록184ms
해결날짜2022/01/11

풀이

  • Disjoint Set을 이용해서 인접한 숫자들을 그룹으로 묶어서 관리하는 테크닉을 사용하는 문제이다.
  • 동일한 테크닉을 사용하는 거의 비슷한 문제로 호텔 방 배정이 있으니, 테크닉에 대한 설명은 그쪽을 참조.
  • 시간복잡도는 n이 비행기의 수, m이 게이트의 수 일때, O(m+n*α(m))이 된다

코드

"""Solution code for "BOJ 10775. 공항".

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

Tags: [Disjoint Set]
"""

import sys
from teflib import disjointset


def main():
    G = int(sys.stdin.readline())
    P = int(sys.stdin.readline())
    g = [int(sys.stdin.readline()) for _ in range(P)]

    dsu = disjointset.DisjointSet(G)
    gate_by_set = list(range(G))
    for i, g_i in enumerate(g):
        set_id = dsu.find(g_i - 1)
        gate = gate_by_set[set_id]
        if gate is None:
            answer = i
            break
        if gate == 0:
            gate_by_set[set_id] = None
        else:
            prev_gate = gate_by_set[dsu.find(gate - 1)]
            gate_by_set[dsu.union(gate, gate - 1)] = prev_gate
    else:
        answer = P

    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
M᠎ X F D M
 
ps/problems/boj/10775.txt · 마지막으로 수정됨: 2022/01/13 08:48 저자 teferi