[CodeTree] 팩맨 - 삼성 SW 역량테스트 2021 하반기 오후 1번 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 분석

• 4x4 격자에 M마리의 몬스터와 1마리의 팩맨이 주어지며, 몬스터는 상하좌우 + 대각선 방향으로 이동이 가능하며 팩맨은 상하좌우로만 이동이 가능함.
• 몬스터 복제
  • 현재 Turn이 K이라 할 때, K번째 Turn이 시작하는 시점에 존재하는 모든 몬스터들이 복제를 위해 알을 낳음.
  • 알은 Turn이 종료되는 시점에 부화를 진행하며, 부화한 몬스터의 방향은 기존 몬스터와 동일함.
• 몬스터 이동
  • 각 몬스터는 (x, y, d)를 가지고 있으며, 현재 위치 및 방향을 기준으로 이동을 시도함.
  • 격자 범위를 벗어나거나, 시체가 있거나 혹은 팩맨이 위치한 좌표로는 이동이 불가능하며, 이러한 경우에는 반시계 방향으로 45' 회전 후 이동이 가능한 좌표가 존재하는지 반복적으로 탐색.
  • 좌표가 존재한다면 해당 방향으로 이동하며 몬스터의 방향은 이동 방향과 동일함.
  • 좌표가 존재하지 않는다면 움직이지 않음.
• 팩맨 이동
  • 팩맨은 매 Turn마다 3차례의 이동을 수행함.
  • 몬스터를 가장 많이 먹는 방향으로 이동을 수행하며, 그러한 경로가 여러가지일 경우 상-좌-하-우의 우선순위에 따라 경로를 선택함.
  • 팩맨 이동 또한 격자를 벗어나는 경로는 존재하지 않음.
  • 최종 움직이면서 경로 위에 있는 모든 몬스터를 먹지만, 부화하지 않은 알은 먹지 않음.
• 시체 소멸
  • 먹힘 당한 몬스터는 격자에서 사라지게 되며, 몬스터가 존재하던 좌표에 시체가 생성됨.
  • 시체는 생성 시점을 기준으로 2 Turn 동안 유지됨.
• 위 과정을 K Turn동안 반복적으로 수행한 후, 격자 위에 존재하는 몬스터의 총 수를 Return하는 문제.

 

문제 접근

• 초기화 단계
  • 몬스터는 8방향 이동은 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 순서이며, 팩맨의 4방향 이동은 ↑, ←, ↓, → 이기 때문에, 8방향을 이동하기 위한 direc 변수를 선언하고, 팩맨 이동 시에는 [0, 2, 4, 6] index만 사용하도록 정의.
  • K Turn이 시작할 때의 몬스터 정보, 복사한 몬스터의 정보를 저장하기 위해 각각 딕셔너리로 정의.
  • 시체 여부를 판단하기 위한 death_field 정의.
• 몬스터 이동
  • 몬스터가 존재하는 각 격자에 접근하여 하나의 몬스터마다 시작 방향을 기준으로 최대 8번의 탐색 과정을 수행.
  • 탐색 과정 중 이동할 수 있는 좌표가 탐색 되었을 때는 cnt의 값이 8보다 작게 되며, 이러한 경우에는 새로운 위치에 몬스터를 이동시키는 작업 수행.
  • 탐색에 실패한 경우 cnt의 값은 8이며, 이러한 경우에는 이동하지 않고 현재 좌표에 몬스터를 그대로 추가하는 작업 수행.
• 팩맨 이동
  • 팩맨의 현재 위치를 시작 지점으로 depth가 3인 BFS를 통해 최적 경로를 탐색함.
  • Queue에는 (x, y, current_path, current_eat_monster)의 정보를 포함하여 탐색을 수행함.
  • 이동했던 좌표로 다시 이동하는 것이 가능함. 동일한 칸을 반복해서 방문할 때, 해당 칸에 몬스터가 존재하는 경우 두 번 이상 먹지 않도록 처리해주는 로직 구현.
  • 최적의 경로가 탐색되었을 때 경로에 따라 팩맨은 이동하며, 이동 시 발견되는 몬스터는 모두 제거하고 시체로 남기는 과정 수행.
• 나머지 과정
  
  • 시체가 2 Turn이상 유지되지 않도록 하기 위한 시체 소멸 과정 수행.
  • 초기에 복제했던 알들이 부화되어 몬스터가 되었기 때문에, 팩맨 이동 및 몬스터 제거가 종료된 딕셔너리에 값을 추가해주는 과정 수행.
  • 원래 몬스터 정보를 포함하는 딕셔너리에 새로 업데이트된 딕셔너리를 복사
• 남은 몬스터의 수를 체크하여 Return 한 후 종료.

 

소스 코드

# define lib
from copy import deepcopy
from collections import deque, defaultdict

# set value from input
num_monster, turn = map(int, input().split())
r, c = [k-1 for k in list(map(int, input().split()))]
direc = [(-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)]
monster_pos = defaultdict(list)
death_field = [[0]*4 for _ in range(4)]

for _ in range(num_monster):
    x, y, d = map(int, input().split())
    monster_pos[(x-1, y-1)].append(d-1)

# run
while turn > 0:
    # copy
    copy_monster_pos = deepcopy(monster_pos)

    # move monsters
    next_monster_pos = defaultdict(list)
    for (cx, cy), cds in monster_pos.items():
        for cd in cds:
            cnt = 0
            while cnt < 8:
                nx, ny = cx+direc[(cd+cnt)%8][0], cy+direc[(cd+cnt)%8][1]
                if nx < 0 or nx >= 4 or ny < 0 or ny >= 4 or (nx, ny) == (r, c) or death_field[nx][ny] > 0:
                    cnt += 1
                    continue
                break
            
            if cnt == 8:
                next_monster_pos[(cx, cy)].append(cd)
            else:
                next_monster_pos[(nx, ny)].append((cd+cnt)%8)
    
    # move packman
    dq = deque([(r, c, [], 0)])
    max_eat, max_path = -1, ""
    while dq:
        cx, cy, cpath, eat_monster = dq.popleft()
        if len(cpath) == 3:
            if max_eat < eat_monster:
                max_eat, max_path = eat_monster, cpath
            continue
        
        for nd in [0, 2, 4, 6]:
            nx, ny = cx+direc[nd][0], cy+direc[nd][1]
            if nx < 0 or nx >= 4 or ny < 0 or ny >= 4:
                continue
            
            if (nx, ny) in cpath:
                dq.append((nx, ny, cpath+[(nx, ny)], eat_monster))
            else:
                dq.append((nx, ny, cpath+[(nx, ny)], eat_monster+len(next_monster_pos[(nx, ny)])))

    # eat monster
    for nr, nc in max_path:
        if len(next_monster_pos[(nr, nc)]) > 0:
            del next_monster_pos[(nr, nc)]
            death_field[nr][nc] = 3
        r, c = nr, nc

    # update death_field
    for i in range(4):
        for j in range(4):
            death_field[i][j] = max(death_field[i][j]-1, 0)

    # copy
    for key in copy_monster_pos.keys():
        next_monster_pos[key].extend(copy_monster_pos[key])

    monster_pos = next_monster_pos
    turn -= 1

count = 0
for value in monster_pos.values():
    count += len(value)
print(count)

• 제출 횟수: 1회
• 풀이 시간: 37분