[알고리즘] 원자 소멸 시뮬레이션

포인트

1. 전형적인 구현 문제이다.

원자가 없을 때 까지 무한 반복

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

python

data = [[0 for _ in range(4001)] for _ in range(4001)]
for test in range(1, int(input()) + 1):

    # 상 하 좌 우
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]

    atoms = []
    n = int(input())
    delete_list = set()
    total_energy = 0
    pop_list = []

    # 음수 없애기
    for _ in range(n):
        y, x, move, energy = map(int, input().split())
        x = (x + 1000) * 2
        y = (y + 1000) * 2
        atoms.append([x, y, move, energy])
        data[x][y] += 1
    # 입력

    # 모든원소가 사라질때까지 반복한다.
    while atoms:
        for i in range(len(atoms)):
            x, y, move, energy = atoms[i]
            nx = x + dx[move]
            ny = y + dy[move]
            # 배열밖으로 벗어난다면 없애버리기

            if not (0 <= nx < 4000 and 0 <= ny < 4000):
                pop_list.append(i)
                continue
            
            data[x][y] -= 1 # 현재 위치 반영
            data[nx][ny] += 1 # 다음 위치 반영
            atoms[i][0], atoms[i][1] = nx, ny # 위치 표시해주기

        # 위치를 벗어났다면 리스트에서 제거
        if pop_list:
            for _ in range(len(pop_list)):
                index = pop_list.pop()
                target_x, target_y = atoms[index][0], atoms[index][1]
                data[target_x][target_y] -= 1
                atoms.pop(index)

        # 리스트를 돌면서 원소가 2개이상인곳 찾기
        for atom in atoms:
            x, y = atom[0], atom[1]
            if data[x][y] >= 2:
                delete_list.add((x, y))

        # 원소가 충돌던위치와 같은 원소를찾아 에너지 더해주기
        if delete_list:
            for x, y in delete_list:
                for i in range(len(atoms) - 1, -1, -1):
                    target_x, target_y, target_energy = atoms[i][0], atoms[i][1], atoms[i][3]
                    if target_x == x and target_y == y:
                        data[target_x][target_y] -= 1
                        total_energy += target_energy
                        atoms.pop(i)
            delete_list.clear()
        # 이렇게 한 사이클 이다

    print("#{} {}".format(test, total_energy))