Sign in Subscribe
PS

[PS] BOJ 24468 / 충돌의 수

Minjun Kim

• 3 min read
[PS] BOJ 24468 / 충돌의 수
문제 링크: https://www.acmicpc.net/problem/24468
Thumbnail: Photo by Mollie Sivaram (Unsplash)

구현 및 시뮬레이션 문제입니다.

풀이

​문제에서 제시된 그대로 구현하면 됩니다.

T초동안 (T초에 발생한 충돌도 포함) 공의 이동을 시뮬레이션 합니다 :

  • 각 공을 이동 방향대로 1칸씩 이동시킵니다.
  • 발생하는 충돌을 처리합니다:
    • 만약 벽 (왼쪽: 위치 0, 오른쪽: 위치 \(L\))에 충돌시
      • 충돌한 공의 방향만 바꿉니다.
    • 만약 다른 공과 충돌 시
      • 두 공의 방향을 바꿉니다.
      • 충돌 횟수를 기록합니다.

현재 상자 안의 공의 위치와, 각 공별로 방향과 현재 위치를 기록해야 합니다.

상자는 world라는 길이 \(L+1\)의 1차원 배열로 표현합니다. (0번과 \(L\)번 위치는 상자의 벽입니다.) 배열의 값으로는 현재 그 위치에 있는 공의 번호 (공 배열의 인덱스)를 기록합니다. 공이 없다면 -1을 기록합니다.

공의 정보는 balls라는 2차원 배열([ [pos, direction] ]) 로 표현합니다. 공의 번호는 자신의 인덱스와 같습니다.

\(T\)초 동안 반복하면서, balls 배열 안의 모든 공에 대해 이동 및 충돌 검사를 수행합니다. 이때, 벽에 충돌하는 경우는 간단히 판정 가능하지만, 다른 공과 충돌하는 경우는 아래와 같이 구현했습니다.

  • 공을 순서대로 이동시키며, world 배열을 갱신합니다.
  • 이후 다른 공이 이동할 때, 자신이 이동할 위치의 world 배열 값이 -1이 아니면 (다른 공이 있으면) 두 공의 충돌 처리를 진행합니다.

전체 코드

input = open(0).readline
L, N, T = map(int, input().split())
world = [-1 for _ in range(L + 1)]      # world[0]과 world[L]은 각각 벽. 배열의 값은 그 위치에 있는 공의 번호.
balls = []                              # balls[[pos, direction]]는 i번 공의 위치와 방향을 각각 기록한다. 

for i in range(N):
    x, d = input().strip().split()
    x = int(x)
    balls.append([x, -1 if d == "L" else 1])
    world[x] = i

count = 0
for t in range(T):  # 1~T초 동안 공을 이동시킨다.
    for idx in range(N):
        pos, direction = balls[idx]
        world[pos] = -1
        new_pos = pos + direction
        if new_pos == 0 or new_pos == L:    # 벽에 부딪히면 방향만 바꾼다.
            balls[idx][1] *= -1
        elif world[new_pos] != -1:          # 다른 공과 부딪히면 두 공의 방향을 바꾸고 충돌 횟수를 기록한다.
            balls[idx][1] *= -1
            count += 1
            other_ball = world[new_pos]
            balls[other_ball][1] *= -1
        world[new_pos] = idx
        balls[idx][0] = new_pos
print(count)

solution.py