[백준 / BOJ] 14595 동방 프로젝트 (Large)

문제

출처 : www.acmicpc.net/problem/14595

14595번: 동방 프로젝트 (Large)

동아리방을 합치는 연산이 여러번 주어졌을때,

이 연산이 모두 끝난후, 남아있는 방의 수를 출력하는 문제다. 

 

풀이

시간초과를 피하기위해 유니온파인드를 이용해서 풀어야한다.

 

방이 총 5개있을때, 각 방은 이런식으로 떨어져있을것이다. (예제 1)

이때, 1번방과 2번방을 합치는 연산을하면 1번방과 2번방은 같은방이되는데, 그걸

이렇게 연결구조로 표현할수있다.

 

다음으로 2번방과 4번방을 합치는 연산을하면,

 

이렇게 표현가능하다.

(나는 작은숫자가 루트노드가 되도록 지정했음)

 

이렇게 합쳐놓으면 방이 합쳐져있는지 확인하는데걸리는 시간복잡도가 O(1)이라서 시간초과를 피할수있다. (자신의 부모가 상대방의 부모와 같은지 확인하면됨)

 

최대방의 갯수가 1,000,000이므로

O(n)번만에 찾을수있다.

 

한번 부순방은 다시 부수지 않도록 주의하자. 부수더라도 답출력에 문제는 없지만, 시간초과가 난다.

1,000,000 * 5000번 돌수있기때문..

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/14595%20%EB%8F%99%EB%B0%A9%20%ED%94%84%EB%A1%9C%EC%A0%9D%ED%8A%B8(Large)/main.swift

devxb/JJUNalgo