[코드트리/삼성SW역량테스트] 팩맨 (Python)

Problem : https://www.codetree.ai/training-field/frequent-problems/problems/pacman/

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

 

Difficulty : Gold 1

 

Status : Solved

 

Time : ??:??:??

 

---

 

문제 설명 / 입력 및 출력

 

 

자세한 설명은 코드트리 사이트 링크를 참조해 주세요!

 

 

---

 

풀이

 

1. 몬스터가 증식하며, 몬스터 수가 100만 단위 비스무리하게 커지는 경우를 제한했으니 수가 매우 많을 것이다. (가로 좌표, 세로 좌표, 몬스터의 방향) 순으로 총 4 * 4 * 8 = 512가지 경우로 나누어 고려해 주는 게 시간적으로 더 효율적이다.

 

2. 팩맨의 이동에 주의하자. 팩맨이 아무 몬스터를 잡을 수 없는 상황이라도 무조건 이동한다. 또한 팩맨의 이동 경우의 수는 4 ^ 3 = 64가지이므로 모든 경우를 테스트해볼 수도 있겠다.

 

풀이 코드

import sys
input = sys.stdin.readline
dr = [-1, -1, 0, 1, 1, 1, 0, -1]
dc = [0, -1, -1, -1, 0, 1, 1, 1]

eggs = [[[0]*8 for _ in range(4)] for _ in range(4)]
monsters = [[[0]*8 for _ in range(4)] for _ in range(4)]
pacman = (-1, -1)
deads = [[0]*4 for _ in range(4)]
move, best_move, best_score = list(), list(), 0

def cloning() :
    for i in range(4) :
        for j in range(4) :
            for k in range(8) :
                eggs[i][j][k] = monsters[i][j][k]

def monster_move() :
    global monsters
    next_monsters = [[[0]*8 for _ in range(4)] for _ in range(4)]
    for r in range(4) :
        for c in range(4) :
            for d in range(8) :
                if not monsters[r][c][d] :
                    continue
                movable = False
                for i in range(8) :
                    ad = (d + i) % 8
                    ar, ac = r + dr[ad], c + dc[ad]
                    if -1 < ar < 4 and -1 < ac < 4 and (ar, ac) != pacman and not deads[ar][ac] :
                        movable = True
                        next_monsters[ar][ac][ad] += monsters[r][c][d]
                        break
                if not movable :
                    next_monsters[r][c][d] += monsters[r][c][d]

    monsters = next_monsters

def dfs(idx, r, c, score) :
    global best_move, best_score
    if idx == 3 :
        if best_score < score :
            best_move, best_score = move[:], score
        return
    
    for i in range(0, 8, 2) :
        if not (-1 < r + dr[i] < 4 and -1 < c + dc[i] < 4) :
            continue
        r += dr[i]
        c += dc[i]
        new_score = score
        if (r, c) not in move :
            new_score += sum(monsters[r][c])
        move.append((r, c))
        dfs(idx+1, r, c, new_score)
        r -= dr[i]
        c -= dc[i]
        move.pop()

def pacman_move() :
    global pacman, best_move, best_score
    move, best_move, best_score = list(), list(), -1
    r, c = pacman    
    dfs(0, r, c, 0)

    for r, c in best_move :
        if sum(monsters[r][c]) > 0 :
            deads[r][c] = 3
            monsters[r][c] = [0]*8
    pacman = tuple(best_move[-1])

def update_dead() :
    for i in range(4) :
        for j in range(4) :
            deads[i][j] = max(deads[i][j]-1, 0)

def cloning_succeed() :
    for i in range(4) :
        for j in range(4) :
            for k in range(8) :
                monsters[i][j][k] += eggs[i][j][k]
                eggs[i][j][k] = 0

m, t = map(int, input().split())
pacman = tuple(map(lambda x : int(x)-1, input().split()))
for _ in range(m) :
    r, c, d = map(int, input().split())
    monsters[r-1][c-1][d-1] += 1

for _ in range(t) :
    cloning()
    monster_move()
    pacman_move()
    update_dead()
    cloning_succeed()


ans = 0
for i in range(4) :
    for j in range(4) :
        ans += sum(monsters[i][j])
print(ans)

풀이 완료!