[Python 3] BOJ - 3163 "떨어지는 개미"

 # 문제 링크 : https://www.acmicpc.net/problem/3163

3163번: 떨어지는 개미

 

 # 풀이 :

 시뮬레이션으로 구현하면 반드시 시간초과에 걸린다. 따라서 시뮬레이션 말고 다른 사고로 접근하는 것이 필요하다. 개인적으로 이 문제의 핵심은 '개미의 인덱스는 절대 바뀌지 않는다는 것, 충돌하지 않는 경우와 실제 충돌하는 경우를 비교하는 것'이다. 시뮬레이션으로 구하다 다른 분들의 설명을 보았기에 이를 참고로 설명하려 한다.

<그림 1. 충돌이 없는 경우>

 위 상황에서 만일 충돌이 없다고 가정하자. 그렇다면 1번 개미는 오른쪽으로 진행할 것이며, 8칸을 더가야 오른쪽 끝에서 떨어질 것이다. 그런데 1초에 1칸을 가므로 ID 1 개미가 오른쪽 끝으로 떨어지는데 걸리는 시간은 8초가 걸릴 것이다. 같은 논리로 ID -2 개미는 3초 후 왼쪽 끝으로, ID -3 개미는 5초 후 왼쪽 끝으로, ID 4 개미는 1초 후 오른쪽 끝으로 떨어질 것이다. 따라서 충돌을 고려하지 않는 경우 떨어지는 순서는 4,-2,-3,1 순이 될 것이다.

ID	1	-2	-3	4
걸리는 시간	8	3	5	1
떨어지는 방향	R	L	L	R

 각 시간대 별로 개미가 떨어지는 시간과, 떨어지는 방향을 구해보자. 현재 ID 4는 앞으로 어떠한 충돌이 일어나지 않을 것이므로, 1초 후 오른쪽으로 떨어질 것이다. 따라서 표를 채우면 아래와 같다

ID	1	-2	-3	4
걸리는 시간	?	?	?	1
떨어지는 방향	?	?	?	R

<그림 1. 1초 후 진행상황>

 첫 충돌이 일어났다. ID 1번 개미는 앞으로 충돌이 일어 날 수가 없으므로 2초 뒤 떨어지는데, 이미 1초가 흐른 뒤이므로 0초 기준으로 3초 후에 왼쪽으로 떨어진다. ID -3도 충돌이 없으므로 1칸 움직여서 현재 위치가 4가 된다. 따라서 표를 채우면 아래와 같다

ID	1	-2	-3	4
걸리는 시간	3	?	?	1
떨어지는 방향	L	?	?	R

<그림 3. 2초 후의 진행상황>

 두번째 충돌이 일어났다. ID 1인 개미는 앞서 설명했듯이, 충돌이 일어나지 않으므로 현재 위치는 1이 된다. 또한 ID -2, -3 개미도 향후 충돌이 일어나지 않기 때문에 각각 3초와 6초 후에 떨어지는데, 이미 2초가 흘렀으므로 총 5초와 8초가 걸리게 된다. 따라서 표를 모두 채울 수 있고 아래와 같다.

ID	1	-2	-3	4
걸리는 시간	3	5	8	1
떨어지는 방향	L	L	R	R

 그런데, 맨 처음 충돌하지 않을 때의 표와 비교한다면, 표는 전체적으로 ID는 다르지만 걸리는 시간과 떨어지는 방향은 일치한다. 즉, 충돌을 고려하든, 고려하지 않든 어떤 개미의 떨어지는 시간과 방향은 변함이 없지만 충돌을 고려하지 않으면 ID가 엉켜버리게 된다. 그런데, 모든 충돌이 일어나면 항상 <- , <- , <- , .... , ->, -> , -> 이런 형태가 되고 개미의 ID는 변함이 없다. 따라서 걸리는 시간이 가장 빠른 개미가 만일 오른쪽에서 떨어진다면, 개미의 진행방향과 상관없이 그냥 오른쪽의 개미가 떨어지는 것이고, 왼쪽으로 떨어진다면 그냥 왼쪽의 개미를 떨어트리면 된다. 

 

 # 코드

import sys, functools, collections
tot = int(sys.stdin.readline())

# 정답을 저장하는 배열
ans = []

# compare : 걸리는 시간이 빠른 순, 만일 걸리는 시간이 같다면 음수 ID순으로 정렬하는 함수
def compare(x,y):
    if x[0] > y[0]:
        return 1
    elif x[0] < y[0]:
        return -1
    else:
        if x[1] > y[1]:
            return 1
        elif x[1] < y[1]:
            return -1
        else:
            return 0

for i in range(tot):
    # 입력부
    n, l, k = map(int, sys.stdin.readline().split())
    
    # ant : 초기 개미들의 상태 저장
    ant = collections.deque()
    
    # order : 충돌을 고려한 실제 떨어지는 순서 저장
    order = []
    
    # nocrash : 충돌을 고려하지 않는 떨어지는 순서 저장
    nocrash = []
    
    
    cnt = 0
    for i in range(n):
        pos, id = map(float, sys.stdin.readline().split())
        ant.append([pos, id])
        nocrash.append([pos, id])
        
    # 충돌하지 않는 경우 걸리는 시간과 방향 계산
    for i in range(n):
        if nocrash[i][1] > 0:
            nocrash[i][0] = l - nocrash[i][0]
            
	# 정렬
    nocrash.sort(key=functools.cmp_to_key(compare))

    while ant:
        # 만일 떨어지는 시간이 같다면
        if cnt != n - 1 and nocrash[cnt][0] == nocrash[cnt + 1][0]:
            # 만일 왼쪽 개미가 음수 ID라면
            if ant[0][1] < ant[-1][1]:
            	# 왼쪽부터 떨어뜨리고 그 다음 오른쪽을 떨어뜨린다
                order.append(ant.popleft())
                order.append(ant.pop())
            # 만일 오른쪽 개미가 음수 ID라면
            else:
            	# 오른쪽부터 떨어뜨리고 그 다음 왼쪽을 떨어뜨린다
                order.append(ant.pop())
                order.append(ant.popleft())
            # 두칸을 건너뛴다
            cnt += 2
            
        # 떨어지는 시간이 다르다면
        else:
            # 왼쪽으로 떨어지면 제일 왼쪽을 떨어뜨린다
            if nocrash[cnt][1] < 0:
                order.append(ant.popleft())
            # 오른쪽으로 떨어지면 제일 오른쪽을 떨어뜨린다
            else:
                order.append(ant.pop())
            cnt += 1
            
    # K번째 순서 저장
    ans.append(order[k - 1])
    
# 정답 출력
for i in ans:
    print(int(i[1]))