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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRFInKex8DFAUo&categoryId=AWXRFInKex8DFAUo&categoryType=CODE&problemTitle=sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

1. 문제 설명

[제약 사항]
 

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거리도 가늠을 해야했으므로 최대 거리인 -1000 ~ 1000(2000) 에서 두배를 곱해 4000으로 만들어서 0.5씩 이동하게 만들었다 2차원 배열을 만들어 시뮬레이션을 실시 했으나 4000*4000의 배열은 메모리를 초과해 배열을 사용하지 않고 딕셔너리로 만들어서 풀었다.

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

T = int(input())
for test_case in range(1, T + 1):
    n = int(input())
    queue = []

    for _ in range(n):
        x, y, d, v = map(int, input().split())
        queue.append([x * 2 + 2000, y * 2 + 2000, d, v])

    e = 0
    while len(queue) >= 2:
        dic = {}
        for x, y, d, v in queue:
            nx = x + dx[d]
            ny = y + dy[d]

            if nx < 0 or nx > 4000 or ny < 0 or ny > 4000:
                continue

            dic[(nx, ny)] = dic.get((nx, ny), [])
            dic[(nx, ny)].append([d, v])
        queue = []

        for a, b in dic.items():
            if len(dic[a]) > 1:
                for i in b:
                    e += i[1]

            else:
                queue.append([a[0], a[1], b[0][0], b[0][1]])

    print(f'#{test_case}', e)