SWEA 5648. 원자 소멸 시뮬레이션(Python)

풀이

처음엔 평소 시뮬레이션 접근하는 거처럼 2차원 배열 생성해서 접근할까했는데,
가로, 세로 범위가 -1000 ~ 1000에 길 중간에서도 만날 수 있으니 다 생성하면
가로 세로 4001개 씩 4001의 제곱 크기의 리스트를 만들어야한다(대충 1600만개).

제한 시간이 15초기도 하고, 1600만 개의 리스트를 생성할 용기도 없으니까
다른 방법으로 좌표를 표현해야한다.

같은 좌표를 리스트로 탐색하는 건 말도 안되니,
딕셔너리의 키를 좌표로 사용하는 걸로 해결하면 된다.

• 처음에 범위가 -1000 ~ 1000으로 정해져있는 건줄 알고 아톰 삭제 안 했다가
  시간초과 났다. 범위 벗어나면 바로바로 삭제해줘야됨~
• 입력 범위 밖에서 아톰들이 서로 만나는 일은 없다.
• 서로 교차하면서 만나는 것도 고려해야하기 때문에 초 단위를 쪼개는게 중요해보인다.

코드

T = int(input())
for tc in range(1, 1+T):
    n = int(input())
    atom = [list(map(int, input().split())) for _ in range(n)]
    # 격자 중간에서 만날 수도 있기 때문에 0.5초 단위로 이동한다고 가정했음
    d = [(0, 0.5), (0, -0.5), (-0.5, 0), (0.5, 0)]

    result = 0

    # 아톰 개수가 2개 이하가 되면 만날 아톰이 없으니까 종료
    while len(atom) >= 2:
        # 모든 아톰을 0.5초 단위로 이동시킨다
        for i in range(len(atom)):
            atom[i][0] = atom[i][0] + d[atom[i][2]][0]
            atom[i][1] = atom[i][1] + d[atom[i][2]][1]

        # 좌표를 딕셔너리로 표현
        location = {}
        # 각 아톰들을 순회하면서 좌표: [아톰들]의 형태로 넣어준다.
        for a in atom:
            try:
                location[(a[0], a[1])].append(a)
            except Exception:
                location[(a[0], a[1])] = [a]

        # 아톰 리스트를 초기화하고
        atom = []
        for l in location:

            if len(location[l]) >= 2:
                # 만약 같은 위치에 아톰이 여러개라면 결과값에 아톰의 에너지들을 결과값에 넣어주고
                for at in location[l]:
                    result += at[3]
            else:
                # 위치에 아톰이 1개라면 범위내에 있는 아톰들은 아톰 리스트에 다시 넣어준다.
                if -1000 <= location[l][0][0] <= 1000 and -1000 <= location[l][0][1] <= 1000:
                    atom.append(location[l][0])

    print(f'#{tc}', result)