[코드트리] 파이썬 - 팩맨

코드트리 - 팩맨

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

 

소요시간 : 3시간 30분

# 접근 방법

• 첫 풀이가 맞왜틀로 계속 헤매었던 문제였는데 사실 시간 초과가 발생했을 것 같다. 2시간이 경과한 후에 다시 로직을 점검하면서 코드를 수정하여 맞출 수 있었다.
• 처음엔 모든 칸을 빈 리스트로 만든 후, 몬스터들의 방향으로 추가해주었지만, 변경 후엔, 각 칸을 8 크기의 리스트로 만든 후 각 방향에 몬스터들의 수로 기록해주었다.
• 또한, 시체 존재 유무를 위한 4x4 크기의 리스트를 생성해주었다.
• T턴 동안 아래 로직으로 진행하였다.
• 몬스터 복제를 위해서 현재 loc_mon을 deepcopy 해준다.
• move_mon 함수를 실행하여 몬스터를 옮겨준다.
  • 옮겨진 위치를 기록하기 위한 temp 리스트를 loc_mon과 같이 생성해준다.
  • 3중 반복문을 통해 loc_mon의 각 칸을 체크하여 몬스터가 있는 경우 check_move() 함수를 통해 다음 위치를 결정한다
  • 현재 위치를 기준으로 반시계로 돌며 이동할 수 있는 방향이 있다면 다음 위치를 return하고 없다면 현재 위치와 방향을 그대로 return 한다
  • 모든 몬스터를 옮긴 후 temp를 loc_mon으로 복사해주고 종료한다.
• move_pack
  • 3중 반복문을 통해 0,0,0 (상상상) 부터 6, 6, 6(우우우)까지 모든 루트를 탐색해준다.
  • 이 때, 격자를 벗어나지 않는 경로 중 가장 많은 몬스터를 먹는 경로를 저장해준다.
  • 탐색이 끝난 후 해당 경로를 순회하며 몬스터가 존재했던 경우 dead에 3으로 기록해주고, loc_mon을 [0] * 8로 초기화해준다.
  • 이후 팩맨의 위치를 route[-1]로 변경해준다.
• loc_dead를 순회하며 -1로 1턴을 깎아준다.
  • 생성되자마자 -1이 되므로 처음에 2가 아닌 3으로 기록을 해주었다.
• loc_egg를 순회하며 부화한만큼 loc_mon에 + 해준다.

import sys
sys.stdin = open('input.txt')
from copy import deepcopy

UP = 0
LEFT_UP = 1
LEFT = 2
LEFT_DOWN = 3
DOWN = 4
RIGHT_DOWN = 5
RIGHT = 6
RIGHT_UP = 7

def move_mon():
    global loc_mon
    temp = [[[0] * 8 for _ in range(4)] for _ in range(4)]
    for i in range(4):
        for j in range(4):
            for d in range(8):
                if loc_mon[i][j][d] > 0:
                    next_i, next_j, next_d = check_move(i, j, d)
                    temp[next_i][next_j][next_d] += loc_mon[i][j][d]

    loc_mon = deepcopy(temp)

def check_move(ci, cj, cd):
    global loc_dead, pi, pj
    cnt = 0
    while cnt < 8:
        ni, nj = ci + di[cd], cj + dj[cd]
        if 0<=ni<4 and 0<=nj<4 and loc_dead[ni][nj] == 0 and (ni, nj) != (pi, pj):
            return ni, nj, cd

        else:
            cnt += 1
            cd = (cd+1) % 8

    return ci, cj, cd

def move_pack(mi, mj):
    global pi, pj
    max_cnt = -1
    route = []
    for i in [0, 2, 4, 6]:
        for j in [0, 2, 4, 6]:
            for k in [0, 2, 4, 6]:
                si, sj = mi ,mj
                temp_cnt = 0
                visit = []
                for d in [i, j, k]:
                    ni, nj = si + di[d], sj + dj[d]
                    if 0<=ni<4 and 0<=nj<4:
                        if [ni, nj] not in visit:
                            temp_cnt += sum(loc_mon[ni][nj])
                        visit.append([ni,nj])
                        si, sj = ni, nj
                    else:
                        break
                else:
                    if temp_cnt > max_cnt:
                        max_cnt = temp_cnt
                        route = visit

    for ri, rj in route:
        for i in range(8):
            if loc_mon[ri][rj][i] > 0:
                loc_dead[ri][rj] = 3
                break
        loc_mon[ri][rj] = [0] * 8

    pi, pj = route[-1]


M, T = map(int, input().split())
pi, pj = map(int, input().split())
pi -= 1
pj -= 1
di, dj = [-1, -1, 0, 1, 1, 1, 0, -1], [0, -1, -1, -1, 0, 1, 1, 1]

loc_mon = [[[0] * 8 for _ in range(4)] for _ in range(4)]
loc_dead = [[0] * 4 for _ in range(4)]
for _ in range(M):
    a, b, c = map(int, input().split())
    loc_mon[a-1][b-1][c-1] += 1


for t in range(T):
    loc_egg = deepcopy(loc_mon)
    move_mon()
    move_pack(pi, pj)
    for i in range(4):
        for j in range(4):
            if loc_dead[i][j] > 0:
                loc_dead[i][j] -= 1

    for i in range(4):
        for j in range(4):
            for k in range(8):
                loc_mon[i][j][k] += loc_egg[i][j][k]

result = 0
for i in range(4):
    for j in range(4):
        result += sum(loc_mon[i][j])

print(result)