[SWEA] 원자 소멸 시뮬레이션

https://swexpertacademy.com/main/main.do

SW Expert Academy

위 그림처럼 원자들이 이동하면서 충돌 소멸하는 시뮬레이션을 구현하는데
좌표값이 -1000 ~ 1000이고 원자들이 충돌하는 시간이 1초일 때, 0.5초일 때가 존재해
해당 부분을 고려해야하는 문제다.

풀이

메모리 초과로 인한 런타임 오류에 대한 문제를 찾지 못해서 많이 고생했다.

data = popleft() 로 받아서 data[0], data[1]... 으로 접근하여 수정 => append(data)
data1, data2, data3 = popleft()로 받아서 접근 후 수정 => append([data1, data2, data3])
위 2가지 경우의 메모리 사용량이 다르다. 메모리 초과도 고려하자.

direction = [[1, 0], [-1, 0], [0, -1], [0, 1]]
# 상 하 좌 우(문제에서는 위로 올라가는 경우를 +로 인식함)

board = [[0] * 4001 for _ in range(4001)]
# 배열, 크기가 4001x4001인 이유는 -1000 ~ 1000을 0 ~ 2000으로 바꾼 후,
# 2를 곱했기 때문(0.5초에 충돌하는 문제를 해결하기 위해 2를 곱했음)

먼저 원자의 이동을 나타낼 direction과 원자들을 표시할 board를 정의했다.
원자간의 거리가 짝수인 경우에는 1초에서 충돌하지만 홀수인 경우에는 0.5초에서 충돌한다.
배열의 크기를 2배로 키우는 것으로 항상 짝수인 경우로 수정하였다.

 

N = int(input())

arr = deque()  # x(j),y(i),위치,에너지
for i in range(N):
    data = list(map(int, input().split()))
    data[0] = (data[0] + 1000) * 2  # 위치 조정
    data[1] = (data[1] + 1000) * 2  # 위치 조정
    board[data[1]][data[0]] = data[3]
    arr.append(data)

N개만큼 원자를 받으면서 위에 board를 수정한 것처럼 원자의 위치도 수정해줬다.

 

    while len(arr) != 0:
        number = len(arr)

        for i in range(number):

            q = arr.popleft()
            now_x, now_y, d, e = q[0], q[1], q[2], q[3]
            next_x, next_y = now_x + direction[d][1], now_y + direction[d][0]

이 부분의 코드가 깔끔하지 못한데, 평소처럼 data를 각 항목에 나눠서 받고 
append할 때 다시 합치는 방법을 사용했더니 메모리 초과가 발생하였다.
4개의 객체를 생성 -> 다시 하나의 임시 객체 생성 후 append하는 작업이 더 메모리를 요구하는 것 같다.

 

            if 0 <= next_y < 4001 and 0 <= next_x < 4001:  # 범위 제한

                if e == board[now_y][now_x]:  # 충돌이 없었으면, 같은 값이어야 함

                    if board[next_y][next_x] == 0:
                        # 아무도 방문하지 않은 곳이면

                        board[now_y][now_x] = 0  # 이전 위치 초기화
                        q[0] = next_x  # 위치 수정
                        q[1] = next_y  # 위치 수정
                        board[next_y][next_x] = e  # 값을 넣어주고
                        arr.append(q)  # 다시 리스트에 집어 넣기

                    else:  # 이미 다른 원자가 한 곳이면
                        board[next_y][next_x] += e
                        # 해당 위치에 자신의 원자 에너지 더해주고

                        board[now_y][now_x] = 0  # 이전 위치 초기화
                        # append 안 함 == 충돌해서 사라지기 때문

                else:  # 충돌 했었으면
                    power += board[now_y][now_x]  # power에 충돌한 에너지 총합 더해주고
                    board[now_y][now_x] = 0  # 현재 위치 초기화

            else:  # 범위 넘어가면(무한대로 간다고 인식)
                # 범위를 때까지 충돌 없으면 이 후에는 무한대로 넘어가도 만나는 경우 없음
                board[now_y][now_x] = 0  # 현재 위치 초기화

같은 진행 방향에서 합쳐지는 경우는 없기 때문에 범위 밖에서 합쳐질 수는 없다.

이번에 deque에서 나온 원자가 충돌하지 않았으면 원자를 이동시킨다.
원자를 이동 시켰을 때 아무 원자도 존재하지 않는 곳이면 dq에 추가하고
이미 다른 원자가 존재하는 곳이라면 그 곳에 값만 더해주는 방식으로 구현했다.

deque에서 나온 원자가 이미 충돌한 상태면 에너지를 방출 = answer에 더해준다.
그리고 board값을 0으로 바꿔준다.

 

전체 코드

from collections import deque

direction = [[1, 0], [-1, 0], [0, -1], [0, 1]]
# 상 하 좌 우(문제에서는 위로 올라가는 경우를 +로 인식함)

board = [[0] * 4001 for _ in range(4001)]
# 배열, 크기가 4001x4001인 이유는 -1000 ~ 1000을 0 ~ 2000으로 바꾼 후,
# 2를 곱했기 때문(0.5초에 충돌하는 문제를 해결하기 위해 2를 곱했음)

T = int(input())

for test_case in range(1, 1 + T):
    N = int(input())

    arr = deque()  # x(j),y(i),위치,에너지
    for i in range(N):
        data = list(map(int, input().split()))
        data[0] = (data[0] + 1000) * 2  # 위치 조정
        data[1] = (data[1] + 1000) * 2  # 위치 조정
        board[data[1]][data[0]] = data[3]
        arr.append(data)

    power = 0
    while len(arr) != 0:
        number = len(arr)

        for i in range(number):

            q = arr.popleft()
            now_x, now_y, d, e = q[0], q[1], q[2], q[3]
            next_x, next_y = now_x + direction[d][1], now_y + direction[d][0]
            if 0 <= next_y < 4001 and 0 <= next_x < 4001:  # 범위 제한

                if e == board[now_y][now_x]:  # 충돌이 없었으면, 같은 값이어야 함

                    if board[next_y][next_x] == 0:
                        # 아무도 방문하지 않은 곳이면

                        board[now_y][now_x] = 0  # 이전 위치 초기화
                        q[0] = next_x  # 위치 수정
                        q[1] = next_y  # 위치 수정
                        board[next_y][next_x] = e  # 값을 넣어주고
                        arr.append(q)  # 다시 리스트에 집어 넣기

                    else:  # 이미 다른 원자가 한 곳이면
                        board[next_y][next_x] += e
                        # 해당 위치에 자신의 원자 에너지 더해주고

                        board[now_y][now_x] = 0  # 이전 위치 초기화
                        # append 안 함 == 충돌해서 사라지기 때문

                else:  # 충돌 했었으면
                    power += board[now_y][now_x]  # power에 충돌한 에너지 총합 더해주고
                    board[now_y][now_x] = 0  # 현재 위치 초기화

            else:  # 범위 넘어가면(무한대로 간다고 인식)
                # 범위를 때까지 충돌 없으면 이 후에는 무한대로 넘어가도 만나는 경우 없음
                board[now_y][now_x] = 0  # 현재 위치 초기화

    print(f'#{test_case} {power}')

코드 자체의 복잡함 보다는 좌표를 어떻게 맵핑을 할 것이고, 충돌하는 경우를 어떻게 설정할 것인지
또 메모리를 어떻게 효율적으로 사용하는지가 중요한 문제였다고 생각한다.