[알고리즘] [모의 SW 역량테스트] 미생물 격리 python(SWEA 5653)

 

코드 풀이 과정

1. 초기 설정:
   • dirs 딕셔너리를 사용하여 각 이동 방향에 따른 좌표 변화를 설정합니다.
   • spin 딕셔너리를 통해 약품 셀에 도달했을 때 반대 방향으로 변환하는 룰을 정의합니다.
2. 입력 받기:
   • N, M, K 값을 입력 받고, 초기 군집 상태를 bugs 리스트에 저장합니다.
3. next 함수 정의:
   • 각 시간 단위마다 군집 이동 및 병합을 계산하는 함수입니다.
   • board 딕셔너리로 이동 후의 각 위치에 대해 군집들을 저장하여 병합할 수 있도록 합니다.
   • 각 위치에서 미생물 수가 가장 많은 군집의 방향을 기준으로 최종 방향을 결정합니다.
   • 가장자리 셀에 도달하면 반대 방향으로 변환하고, 미생물 수를 절반으로 줄이는 처리를 수행합니다.
4. 격리 시간 반복 처리:
   • for _ in range(M) 루프를 통해 M 시간 동안 next 함수를 반복 호출하여 군집 상태를 갱신합니다.
5. 결과 계산:
   • 최종 남아 있는 모든 군집의 미생물 수를 합산하여 반환합니다.

 

주요 변수와 이동 처리 과정

1. 이동 방향과 회전 방향 설정
   • dirs 딕셔너리: 각 방향에 대해 (행 변화량, 열 변화량)을 설정해줍니다.
     • 1: 상 (위쪽, (-1, 0))
     • 2: 하 (아래쪽, (1, 0))
     • 3: 좌 (왼쪽, (0, -1))
     • 4: 우 (오른쪽, (0, 1))
   • spin 딕셔너리: 약품이 있는 셀에 도달할 때 방향을 반대로 바꾸기 위해 각 방향에 대한 반대 방향을 설정합니다.
     • 상 ↔ 하 (1 ↔ 2), 좌 ↔ 우 (3 ↔ 4)
2. 미생물 이동 및 군집 모으기
   • next() 함수는 한 시간 동안의 미생물 이동을 처리하는 함수로, 다음과 같은 과정을 따릅니다:
     • board 딕셔너리: 새로운 위치에 군집을 저장하여 동일 위치에 여러 군집이 모일 경우 합쳐지도록 합니다.
       • 키는 (nextRow, nextCol)의 형태로 위치 좌표이고, 값은 그 위치에 있는 미생물들의 (미생물 수, 이동 방향) 리스트입니다.
     • bugs 리스트: 현재 시간에 존재하는 모든 군집을 하나씩 불러와 이동을 수행합니다.
     • bugs의 각 요소인 (row, col, count, dir)를 불러와, 각 군집이 dir에 맞는 방향으로 한 칸 이동하여 (nextRow, nextCol)의 새로운 위치를 계산합니다.
     • board 딕셔너리에 새로운 위치 (nextRow, nextCol)를 키로 하여 미생물 수와 이동 방향을 리스트 형태로 추가합니다
     • board.get((nextRow, nextCol), [])는 board에 해당 위치가 이미 존재하는지 확인하여, 해당 위치에 군집이 모일 수 있도록 리스트를 덧붙여줍니다

for bug in bugs:
    (row, col, count, dir) = bug
    dirV = dirs[dir]
    nextRow, nextCol = dirV[0] + row, dirV[1] + col
    board[(nextRow, nextCol)] = board.get((nextRow, nextCol), []) + [(count, dir)]

 

 

 

 

같은 위치에 모인 군집 합치기

이동 후 board에 같은 위치에 여러 군집이 모였을 경우 처리하는 코드입니다.

 

• board.items()로 각 위치와 해당 위치에 있는 군집들의 리스트를 가져옵니다.
• maxdValue = max(value): 미생물 수가 가장 큰 군집을 찾아 currentDir에 그 군집의 이동 방향을 할당합니다. 이 방향은 합쳐진 군집의 이동 방향이 됩니다.
• currentCount = sum(list(map(lambda x: x[0], value))): 해당 위치에 있는 모든 군집의 미생물 수를 합산하여 새로운 군집의 미생물 수로 설정합니다.

currentBugs = []
for key, value in board.items():
    row, col = key
    maxdValue = max(value)
    currentDir = maxdValue[1]
    currentCount = sum(list(map(lambda x: x[0], value)))

 

 

약품 칠해진 셀에서의 처리

• 만약 현재 군집의 위치가 가장자리 셀이면, 군집의 이동 방향을 spin 딕셔너리에서 반대로 변경하고, 미생물 수를 반으로 줄입니다.

if row == 0 or row == N -1:
    currentDir = spin[currentDir]
    currentCount = currentCount // 2
elif col == 0 or col == N - 1:
    currentDir = spin[currentDir]
    currentCount = currentCount // 2

 

 

시간 경과에 따른 반복

주어진 시간이 M만큼 경과할 때까지 next() 함수를 반복 호출하여, 각 시간마다 군집의 이동과 충돌, 약품 처리 등을 수행합니다.

 

정답 코드

import sys
input = sys.stdin.readline

def sol():
    # 미생물 군집이 이동하는 방향 설정 (상: 1, 하: 2, 좌: 3, 우: 4)
    dirs = {1: (-1, 0), 4: (0, 1), 3: (0, -1), 2: (1, 0)}
    
    # 입력 값 받기 (N: 구역 크기, M: 격리 시간, K: 초기 군집 수)
    N, M, K = list(map(int, input().split()))
    
    # 초기 군집 정보 (row: 세로 위치, col: 가로 위치, count: 미생물 수, dir: 이동 방향)
    bugs = []
    for _ in range(K):
        bugs.append(tuple(map(int, input().split())))
    
    # 방향 반전 설정 (상 <-> 하, 좌 <-> 우)
    spin = {1: 2, 2: 1, 3: 4, 4: 3}
    
    # 한 시간 경과 후의 군집 상태를 계산하는 함수 정의
    def next():
        nonlocal bugs
        board = {}
        
        # 각 군집의 다음 위치 계산
        for bug in bugs:
            (row, col, count, dir) = bug
            dirV = dirs[dir]
            nextRow, nextCol = dirV[0] + row, dirV[1] + col
            
            # 다음 위치에 군집 정보 추가
            board[(nextRow, nextCol)] = board.get((nextRow, nextCol), []) + [(count, dir)]
        
        currentBugs = []
        
        # 모든 위치에 대해 군집 업데이트
        for key, value in board.items():
            row, col = key
            # 가장 많은 미생물 수를 가진 군집의 방향 설정
            maxdValue = max(value)
            currentDir = maxdValue[1]
            currentCount = sum(list(map(lambda x: x[0], value)))
            
            # 가장자리 약품 셀에 도달한 경우 처리
            if row == 0 or row == N - 1:
                currentDir = spin[currentDir]
                currentCount = currentCount // 2
            elif col == 0 or col == N - 1:
                currentDir = spin[currentDir]
                currentCount = currentCount // 2
            
            # 현재 위치의 최종 군집 정보 업데이트
            currentBugs.append((row, col, currentCount, currentDir))
        
        # 군집 상태 갱신
        bugs = currentBugs

    # M 시간 동안 군집 이동 및 병합 반복
    for _ in range(M):
        next()
    
    # 최종 남은 미생물 수의 총합 계산
    return sum(list(map(lambda x: x[2], bugs)))

# 테스트 케이스 별 결과 출력
for ind in range(int(input())):
    print(f"#{ind + 1} {sol()}")