SWEA 5648 원소 소멸 시뮬레이

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRFInKex8DFAUo

요약: 원자들이 소멸되면서 방출하는 에너지의 총합을 구하는 프로그램을 작성

원자들이 좌표공간안에서 이동하고, 충돌 여부를 검사해야하는 문제이다.

원자들은 -1000 ~ 1000 사이의 좌표에 존재할 수 있다.
하지만 원자는 이동중에도 충돌할 수가 있다.
예를 들어

• A: (0, 0) 오른쪽 방향
• B: (1, 0) 왼쪽 방향

두 원자는 (0.5, 0) 지점에서 충돌할 수 있다.
만약 문제의 조건대로 1씩 원자를 움직인다면 이러한 충돌을 고려 할 수 없다.
즉 모든 공간을 트랙킹 하려고 하면 최소 4000 * 4000 만큼의 좌표 공간을 고려해야한다.
하지만 이것은 공간 복잡도를 매우 증가시킨다.

따라서 원자들의 위치를 관리할 아이디어가 필요하다.

가장 간단하게 사용할 수 있는 것이 python의 dictionary(map) 이다.

모든 원자가 서로 다른 위치에 있다고 한다고 해도, 제한이 1000개이기 때문에 1000개의 좌표만 관리하면 된다.

따라서 grid = defaultdict(list) 를 활용해서 좌표공간을 관리한다.

원자가 더이상 충돌할 수 없을 때 까지 1-3을 반복한다.

1. grid에 각 원자들을 배치한다.
2. grid의 정보를 토대로 동일한 좌표에 있는 원자들을 충돌시킨다. (에너지 sum)
3. 충돌하지 않은 원자들은 다시 리스트화한다.

이를 구현하면 아래와 같다.

전체 코드

"""
Author:
    Name: KyungHyun Lim
    Email: lkh1075@gmail.com
"""

from collections import defaultdict

# 원자 이동 가능 방향
# 상, 하, 좌, 우
dx = [0, 0, -0.5, 0.5]
dy = [0.5, -0.5, 0, 0]

N = 0 # 원자개수
energy = 0 # 에너지 총량

def move(atom_info, ):
    global dx, dy, N, energy

    while len(atom_info) > 1:
        grid = defaultdict(list)
        for atom in atom_info: # 원자 위치 표시
            x, y, d, k = atom
            grid[(x + dx[d], y + dy[d])].append([x + dx[d], y + dy[d], d, k])
        atom_info = []
        
        for cord, atoms in grid.items():
            if len(atoms) > 1: # 동일 위치에 있는 원자 제거
                for values in atoms:
                    energy += values[-1]
            else: # 범위 내 원자 정보 저장
                if -1000 <= cord[0] <= 1000 and -1000 <= cord[1] <= 1000:
                    atom_info += atoms

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input()) # 원자 개수 입력
    
    atom_info = []
    energy = 0
    for _ in range(N): # 원자 정보 입력
        # x, y, d(이동 방향), k(에너지)
        atom_info.append(list(map(int, input().split())))

    move(atom_info)
    print(f'#{test_case} {energy}')