[백준/골드4] [20040] 사이클 게임 - python, Pypy 3

사이클 게임

문제내용 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다. C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다. 문제는 선분을 여러 개 그리다 보면 사이클이 완성 되었는지의 여부를 판단하기 어려워 이미 사이클이 완성되었음에도 불구하고 게임을 계속 진행하게 될 수 있다는 것이다. 이 문제를 해결하기 위해서 게임의 진행 상황이 주어지면 몇 번째 차례에서 사이클이 완성되었는지, 혹은 아직 게임이 진행 중인지를 판단하는 프로그램을 작성하려 한다. 입력으로 점의 개수 n과 m 번째 차례까지의 게임 진행 상황이 주어지면 사이클이 완성 되었는지를 판단하고, 완성되었다면 몇 번째 차례에서 처음으로 사이클이 완성된 것인지를 출력하는 프로그램을 작성하시오. 입력방식 입력은 표준입력을 사용한다. 입력의 첫 번째 줄에는 점의 개수를 나타내는 정수 3 ≤ n ≤ 500,000 과 진행된 차례의 수를 나타내는 정수 3 ≤ m ≤ 1,000,000 이 주어진다. 게임에서 사용하는 n개의 점에는 0 부터 n − 1 까지 고유한 번호가 부여되어 있으며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 이어지는 m 개의 입력 줄에는 각각 i번째 차례에 해당 플레이어가 선택한 두 점의 번호가 주어진다 (1 ≤ i ≤ m).

---

프로그래밍 순서

입력된 데이터를 트리를 만든다고 생각하고 풀었다.

1. 각 점의 root가 되는 점을 담는 parent 리스트를 생성한다.

2. 선택된 두 점을 트리로 연결하기 위해 union 함수 넣는다.

  2-1 find 함수에서 각 점의 root 점이 무엇인지 찾는다.

  2-2 만약 두 점의 root점이 같다면 사이클이 생성된 것이기 때문에 True를 반환한다.

  2-3 만약 두점의 root점이 같지 않다면 두 점 중 큰 점의 parent를 작은 점의 root로 바꾼다.

3. union에서 True를 반환받았다면 현재 몇 번쨰 차례였는지 출력한 후 for문을 멈춘다.

---

전체코딩

 

- 코드

# 20040 사이클 게임
 
def find(x, parent):
    if x == parent[x]:
        return x
    else:
        y = find(parent[x], parent)
        parent[x] = y
        return y
 
def union(x, y, parent):
    x = find(x, parent)
    y = find(y, parent)
    
    if x == y: # 사이클이 만들어졌을 경우
        return True
    elif x < y:
        parent[y] = x
    else:
        parent[x] = y
    return False
 
#입력
dotNum, progressNum = map(int, input().split())
data = [map(int, input().split()) for _ in range(progressNum)]
        
parent = [i for i  in range(dotNum)]
for i, [dot1, dot2] in enumerate(data):
    check = union(dot1, dot2, parent)
    if check:
        print(i+1)
        break
else:
    print(0)
 

 

---

Python3으로 계속해서 에러가 나서 계속 수정하다가 Pypy3로 돌리니 시간초과 없이 통과되었다!