(Python/파이썬) - 백준(BOJ) 3221번 : 개미의 이동

https://www.acmicpc.net/problem/3221

3221번: 개미의 이동

---

• 문제 : 

크기를 무시할 수 있는 개미 여러 마리가 줄 위를 일정한 속도 1mm/s로 걸어가고 있다.

 

개미가 장애물 (줄의 끝이나 다른 개미)을 만나면, 그 즉시 방향을 바꾸고 같은 속도로 계속 걸어가게 된다.

 

개미의 처음 위치와 방향 (왼쪽 또는 오른쪽)이 주어진다. 개미는 1번부터 N번까지 왼쪽에 있는 개미부터 차례대로 번호가 매겨져 있다. 두 개미의 처음 위치가 같은 경우는 없다.

 

T초가 지난 후에 모든 개미의 위치를 구하는 프로그램을 작성하시오. 

 

 

 

---

• 풀이 :

구현 문제였습니다.

아이디어를 생각하기가 까다로웠던 문제입니다

 

우선, 가장 직관적인 방법인 T초의 시간동안 N마리의 개미들을 하나씩 확인하며 좌표를 변경하는 방법은O(T * N)로 최대 1,000,000 * 70,000 의 연산을 실행하여 시간초과에 걸립니다. 

 

문제의 핵심은 모든 개미가 동시에 움직인다는 것입니다. 

 

만약 일직선상의 길 위에서 개미 두 마리가 마주보는 방향으로 무한대의 시간동안 진행한다면 언젠간 두 개미는 만나 방향을 바꾸게 될 것입니다.

 

이 때, 각각의 개미를 독립된 개체로 보지 않고 구별이 불가능한 개체 (예를 들어, 모든 개미가 숫자 1로 표현된다고 한다면) 숫자 1끼리 만났을 때 실제로 동작은 서로 방향을 바꾸어 반대방향으로 진행하겠지만 보이기엔 1은 진행 방향 그대로 직진하는 것처럼 보일 것입니다. 

 

예시) 아래에서 ㅡ는 빈공간, 1은 개미라고 칭하고 왼쪽 개미는 오른쪽으로, 오른쪽 개미는 왼쪽으로 진행한다고 가정하겠습니다.

 

0초  =>  1ㅡㅡㅡ1

1초  =>  ㅡ1ㅡ1ㅡ

2초  =>  ㅡㅡ1ㅡㅡ  (만나서 서로 방향을 바꿈)

3초  =>  ㅡ1ㅡ1ㅡ

4초  =>  1ㅡㅡㅡ1   (벽에 부딪혀 방향을 바꿈)

5초  =>  ㅡ1ㅡ1ㅡ

.

.

 

개미는 시간의 흐름에 따라 위와 같이 진행합니다.  규칙이 보이시나요? 실제로 개미는 서로, 또는 벽에 부딪혀 같은 구간을 반복하여 움직이고 있지만 겉으로 보았을 때 개미는 진행 방향 그대로 쭉 직진하는 것처럼 보입니다. (벽에는 튕깁니다.)

 

따라서, 우리는 모든 개미에 대해 서로 부딪히는 경우를 고려하지 않고 처음 주어진 진행방향대로 T초동안 이동했을 때의 위치만을 찾으면 됩니다. 문제에서 요구하는 각 개미들의 번호 순서대로 출력하는 것은 모든 개미가 움직인 후 이를 오름차순 정렬하면 됩니다. 그 이유는 위에서 보았듯이 각 개미는 같은 구간만을 반복하여 움직이게 됩니다. 즉, 순서가 절대로 바뀌지 않는다는 것입니다.

 

결과적으로, 모든 개미에 대해 처음 주어진 방향대로 T초간 이동했을때의 위치를 구하기 위해 개미가 벽에 부딪혀 방향을 바꾸는 경우만 고려하면 됩니다.

 

풀이입니다.

 

1. 처음 진행방향이 왼쪽과 오른쪽인 경우로 나눕니다.

 

2. 각 경우마다 개미가 이동한 총 거리를 계산합니다. 저의 경우, 오른쪽 진행일 경우 좌표 0에서부터 (처음 위치) + (T초간 움직일 거리)를 총 움직인 거리로 하였고 왼쪽 진행일 경우 좌표 L-1에서부터 (L-처음 위치) + (T초간 움직인 거리)를 총 움직인 거리로 계산했습니다. 

 

3. 이동한 총 거리가 L보다 작다면 그 거리만큼 이동한 값을 answer 배열에 넣어줍니다. 아니라면 L보다 긴 거리를 이동했다는 것이므로 반드시 벽에 1회 이상 튕기게 됩니다. 벽에 짝수만큼 튕긴 경우와 홀수만큼 튕긴 경우로 나누어 계산해주었습니다.

 

4. 각 개미들이 T초동안 움직여서 최종적으로 도착하는 좌표들을 담은 answer 배열을 오름차순 정렬하여 양식에 맞게 출력합니다.

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

L,T  = map(int,input().split())
N = int(input())
ant = []
answer = []
for _ in range(N):
    pos, dir = input().split()
    ant.append([int(pos),dir])

for i in range(N):
    if ant[i][1] == "L": # 왼쪽으로 이동하는경우
        move = T+L-ant[i][0] # 개미가 이동한 칸
        if move < L: # 개미가 L보다 작은 길이를 이동한 경우
            answer.append(L-move)
        else:
            if (move//L) % 2 == 1: # 개미가 이동한 거리가 L의 홀수배수일 경우
                answer.append(move%L)
            else:
                answer.append(L - move%L)
    else: # 오른쪽으로 이동하는 경우
        move = T + ant[i][0]
        if move < L:
            answer.append(move)
        else:
            if (move//L) % 2 == 1:
                answer.append(L - move%L)
            else:
                answer.append(move%L)
answer.sort()
print(' '.join(map(str,answer)))