원자소멸시뮬레이션(SW Expert Academy, SWEA)

난이도 : 모의 SW 역량테스트

문제번호 : 5648

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRFInKex8DFAUo&categoryId=AWXRFInKex8DFAUo&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

원자력 발전소에서 근무하는 상원이는, 발전소에서 발생하는 에너지를 미리 계산하기 위해 원자들의 움직임을 시뮬레이션 하는 프로그램을 만들려고 한다. 원자들은 2차원 평면에서 이동하며 두 개 이상의 원자가 충돌 할 경우 충돌한 원자들은 각자 보유한 에너지를 모두 방출하고 소멸된다. 원자의 움직임은 다음과 같다.   1. 원자의 최초 위치는 2차원 평면상의 [x, y] 이다. 2. 원자는 각자 고유의 움직이는 방향을 가지고 있다. (상하좌우 4방향)  - 상: y 가 증가하는 방향  - 하: y 가 감소하는 방향  - 좌: x 가 감소하는 방향  - 우: x 가 증가하는 방향 3. 모든 원자들의 이동속도는 동일하다. 즉, 1초에 1만큼의 거리를 이동한다. 4. 모든 원자들은 최초 위치에서 동시에 이동을 시작한다. 5. 두 개 이상의 원자가 동시에 충돌 할 경우 충돌한 원자들은 모두 보유한 에너지를 방출하고 소멸된다. [그림-1] 과 같이 원자들의 [x, y] 위치와 이동방향이 주어지고 각 원자들의 보유 에너지가 1 이라고 가정해보자. (실제 입력에서 원자들의 보유 에너지는 각각 다를 수 있다.) 충돌된 원자들이 소멸하면서 방출하는 에너지는 다음과 같다. 1초 후에 I, J 원자가 충돌 후 소멸하면서 2 에너지 방출 1.5초 후에 A, B 원자가 충돌 후 소멸하면서 2 에너지 방출 2초 후에 D, E, G, H 원자가 충돌 후 소멸하면서 4 에너지 방출 3초 후에 M, N 원자가 충돌 후 소멸하면서 2 에너지 방출 [그림-1]의 경우 시간이 흘러도 원자 C, F, K, L 은 영원히 충돌하지 않아 소멸되지 않는다. 따라서 원자들이 소멸되면서 방출하는 에너지의 총합은 10 이다. N 개의 원자들의 [x, y] 위치, 이동 방향, 보유 에너지가 주어질 때 원자들이 소멸되면서 방출하는 에너지의 총합을 구하는 프로그램을 작성하라.

 

제약사항

1. 원자들의 수 N 은 1,000개 이하이다. (1≤N≤1,000) 2. 각 원자들의 보유 에너지 K 는 1 이상 100 이하이다. (1≤K≤100) 3. 원자들의 처음 위치 [x, y] 는 -1,000 이상 1,000 이하의 정수로 주어진다. (-1,000≤x,y≤1,000) 4. 원자들은 2차원 평면 위에서 움직이며 원자들이 움직일 수 있는 좌표의 범위에 제한은 없다. 5. 원자들의 이동 방향은 상(0), 하(1), 좌(2), 우(3)로 주어진다. 6. 원자들은 동시에 1초에 이동 방향으로 1만큼 이동한다. 7. 원자들의 최초 위치는 서로 중복되지 않는다. 8. 원자들은 2개 이상의 원자들이 서로 충돌할 경우 보유한 에너지를 방출하면서 바로 소멸된다. 9. 원자들은 이동 방향은 처음에 주어진 방향에서 바뀌지 않는다. 10. 원자들이 충돌하여 소멸되며 방출되는 에너지는 다른 원자의 위치나 이동 방향에 영향을 주지 않는다.

 

입력

입력의 가장 첫 줄에는 총 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터는 각 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 원자들의 수 N이 주어진다. 다음 N개의 줄에는 원자들의 x 위치, y 위치, 이동 방향, 보유 에너지 K가 주어진다. 원자들의 이동 방향은 상(0), 하(1), 좌(2), 우(3)로 주어진다.

출력

테스트 케이스 T에 대한 결과는 “#T”을 찍고, 방출되는 에너지의 총합을 출력한다. (T는 테스트케이스의 번호를 의미하며 1부터 시작한다. )

예시

입력	출력
2 4 -1000 0 3 5 1000 0 2 3 0 1000 1 7 0 -1000 0 9 4 -1 1 3 3 0 1 1 1 0 0 2 2 -1 0 0 9	#1 24 #2 0

---

2. 문제풀이

원자는 동시에 이동하기때문에 0.5구간에서 만나는 경우가 생긴다. 이걸 처리하지 않아서 테스트 케이스중 몇개가 실패했었다. 따라서 원자를 표시하는 맵을 2배크기로 키워주고 0.5를 1로 올려서 계산한다. 또한 인덱스 계산을 위해 양수로 보정했다. 원자의 정보를 담은 리스트를 하나 만들어서 저장한 후 리스트가 빌때까지 프로그램을 동작시켰다. 원자를 맵에서 하나하나 이동시키다가 충돌이 일어나면 충돌포인트를 저장한 뒤 충돌포인트가 있다면 충돌한 원자를 전부찾아서 없애주는 작업을 했다. 없애줄때 가지고 있는 에너지를 따로 변수에 더 해주면 끝난다.

---

3. 소스코드

#5648 모의역량테스트 원자소멸 시뮬레이션
position_list = [[0 for _ in range(4001)] for _ in range(4001)]
T = int(input())
for t in range(1, T+1):
    #상 하 좌 우
    move_list = [(1, 0), (-1, 0), (0, -1), (0, 1)]
    atom_list = []
    length = int(input())
    remove_list = set()
    energy_sum = 0
    
    #위치보정
    #0.5구간이 생길수있어서 2배로 늘려준다.
    #인덱스 접근을 위해 양수로 보정한다.
    for _ in range(length):
        x, y, move , energy = map(int, input().split())
        y = (y+1000)*2
        x = (x+1000)*2
        atom_list.append([y, x, move, energy])
        position_list[y][x] += 1
        pop_list = []
#모든원소가 사라질때까지 반복한다.
    while atom_list:
        for i in range(len(atom_list)):
            y, x, move, energy = atom_list[i]
            move_y = y + move_list[move][0]
            move_x = x + move_list[move][1]
            #배열밖으로 벗어난다면 없애버리기
            if move_x < 0 or move_x > 4000 or move_y < 0 or move_y > 4000:
                pop_list.append(i)
                continue
            #현재위치에서 삭제하고
            position_list[y][x] -= 1
            #다음위치로이동
            position_list[move_y][move_x] += 1
            #위치 표시해주기
            atom_list[i][0], atom_list[i][1] = move_y, move_x
        #위치를 벗어났다면 리스트에서 제거
        if pop_list:
            for _ in range(len(pop_list)):
                index = pop_list.pop()
                t_y, t_x =  atom_list[index][0], atom_list[index][1]
                position_list[t_y][t_x] -=1
                atom_list.pop(index)
        
        #리스트를 돌면서 원소가 2개이상인곳 찾기
        for i in atom_list:
            y, x = i[0], i[1]
            if position_list[y][x] > 1:
                remove_list.add((y,x))
        #원소가 충돌던위치와 같은 원소를찾아 에너지 더해주기
        if remove_list:
            for y, x in remove_list:
                for i in range(len(atom_list)-1, -1, -1):
                    t_y, t_x, t_e = atom_list[i][0], atom_list[i][1], atom_list[i][3]
                    if t_y == y and t_x == x:
                        position_list[t_y][t_x] -=1
                        energy_sum += t_e
                        atom_list.pop(i)
            remove_list.clear()
 
    print("#{} {}".format(t, energy_sum))