[SWEA] 2382 : 미생물 격리 - Python

문제

NxN 보드, 가장 바깥쪽 가장자리 부분에 위치한 셀들에는 특수한 약품이 칠해져 있다.
초기 세팅 : 각 미생물 군집의 위치, 군집 내 미생물의 수, 이동방향 주어진다.

1시간마다 이동방향에 있는 다음 셀로 이동
1-1. 미생물 군집이 이동 후 약품이 칠해진 셀(가장 바깥족) 도착 시 군집 내 미생물의 절반이 죽고, 이동방향 반대
1-2. 미생물 수가 홀수인 경우 살아남은 미생물 수 = 원래 미생물 수 2로 나눈 후 소수점 이하 버림

2-1. 이동 후 두개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다.
2-2. 합쳐진 군집의 미생물 수는 군집들의 미생물 수의 합, 이동 방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향. (미생물 수가 같은 경우는 주어지지 않음)

M시간 동안 미생물 격리 후 남아있는 미생물 총합 구하기

내 코드

import sys
from collections import deque, defaultdict

sys.stdin = open("input.txt", "rt")

# 상 하 좌 우 : 1 2 3 4
dx = [0,-1,1,0,0]
dy = [0,0,0,-1,1]

def isInner(x,y):
    if 1<=x<n-1 and 1<=y<n-1:
        return True # 약품 외 내부는 안전
    return False # 이 경우는 약품에 도달한 경우

def BFS():
    global dq
    time = 0 # 시간 시간
    res = 0
    while dq:
        time += 1 # 시간이 
        size = len(dq) # 시간에 따라서 진행해야 하므로 현재 시간에 저장되어 있는 애들만 돌아야지
        check = defaultdict(list) # 이동할 좌표의 겹침을 해결하기 위해
        for _ in range(size):
            x,y,cnt,d = dq.popleft() # 현재 미생물 군집의 좌표, 미생물 개수, 방향
            nx = x + dx[d]
            ny = y + dy[d]
            if not isInner(nx,ny): # 약품에 들어간 경우
                cnt = int(cnt/2)
                if d == 1: d = 2
                elif d == 2: d = 1
                elif d == 3: d = 4
                elif d == 4: d = 3
                dq.append((nx,ny,cnt,d))
            if isInner(nx,ny): # 이동 가능
                check[(nx,ny)].append((cnt,d)) # 현재 좌표에 미생물 개수, 방향을 일단 넣어두기


        # 현재 타입에서 모두 확인한 후 이제 겹치는지 확인하면서 큐에 넣기
        for (nx,ny), val in check.items():
            if len(val) == 1: # 특정 좌표에 딱 하나 존재한다면
                dq.append((nx,ny,val[0][0], val[0][1])) # 그대로 추가
            elif len(val) > 1: # 특정 좌표에 여러개가 존재
                cnt_sum = 0
                cnt_max = 0
                idx = 0
                for i in range(len(val)): # 하나씩 확인하면서 최대값
                    cnt_sum += val[i][0] # 미생물 개수는 다 더해주고
                    if val[i][0] > cnt_max:
                        cnt_max = val[i][0]
                        idx = i
                d = val[idx][1]
                dq.append((nx,ny,cnt_sum,d))
        # print(f"{time}초 지난 후 미생물 군집 상황")
        # for now in dq:
        #     print(f"좌표 : {now[0], now[1]}, 미생물 수 : {now[2]} 방향 : {now[3]}")


        if time == m: # 해당 시간에 도달하면 현재까지 존재하는 미생물 수 합 반환
            for now in dq:
                res += now[2]
            return res
            break



T = int(input())
for t in range(1,T+1):
    n,m,k = map(int, input().split())
    # k개의 미생물 군집의 정보
    dq = deque()
    for _ in range(k):
        x,y,cnt, d = map(int, input().split()) # 해당 군집의 x,y,미생물 개수,방향
        dq.append((x,y,cnt,d))

    res = BFS()
    print(f"#{t} {res}")

코멘트

해당 문제는 겹칠 때가 가장 문제였다.
나는 일단 내부라면 해당 좌표에 대해서 딕셔너리로 모두 저장해놓고 다시 한번 돌려서 가장 큰 값을 반환하도록 함.