[코드트리] - 팩맨

https://www.codetree.ai/training-field/frequent-problems/problems/pacman?page=1&pageSize=20 

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

문제유형

dx dy technique, 구현

 

풀이시간

설계: 10분 구현: 180분

풀이방법

빡구현 문제, 특정 시점에 생존해 있는 몬스터가 최대 100만 인것에 주의해야한다. 모든 몬스터의 위치를 배열안에 저장하면 시간 초과가 발생할 수 있다.

 

문제 설명에서 주의해야 할 부분은 몬스터의 시체는 몬스터가 존재하는 곳에만 생성된다는 것이다.

팩맨 이동 경로를 구하고 그 이동 경로 좌표 전부에 몬스터 시체 정보를 갱신해줘서 2시간을 날린 문제..

코드

# 상부터 반시계 방향 45도
mdx, mdy = [-1, -1, 0, 1, 1, 1, 0, -1], [0, -1, -1, -1, 0, 1, 1, 1]
# 상 좌 하 우 순 팩맨 이동 정보
pdx, pdy = [-1, 0, 1, 0], [0, -1, 0, 1]


def in_range(x, y):
    return 1 <= x <= 4 and 1 <= y <= 4


def main():
    ans = 0
    #  몬스터 수, 반복 횟수
    M, T = map(int, input().split())
    # 팩맨 위치
    R, C = map(int, input().split())

    # 살아있는 몬스터 정보 3차원 배열 [x][y][d],
    m_arr = [[[0] * 8 for _ in range(5)] for _ in range(5)]
    for i in range(M):
        mx, my, md = map(int, input().split())
        md -= 1
        m_arr[mx][my][md] += 1

    # 시체정보
    die_arr = [[-1] * 5 for _ in range(5)]

    for turn in range(T):
        # 몬스터 복제 시도 (x,y,d, diff)
        m_copy_info = []
        for r in range(1, 5):
            for c in range(1, 5):
                for k in range(8):
                    if m_arr[r][c][k] != 0:
                        m_copy_info.append((r, c, k, m_arr[r][c][k]))

        m_move_info = []
        # 몬스터 이동
        for r in range(1, 5):
            for c in range(1, 5):
                for k in range(8):
                    # 몬스터 정보가 없을때는 무시
                    if m_arr[r][c][k] == 0:
                        continue
                    # 반시계 방향으로 돌며
                    for dd in range(8):
                        nd = (k + dd) % 8
                        nx, ny = r + mdx[nd], c + mdy[nd]
                        # 갈수 있고 시체가 아니고 팩맨이 아닐때 이동시키고 브레이크
                        if in_range(nx, ny) and turn > die_arr[nx][ny] and (nx, ny) != (R, C):
                            diff = m_arr[r][c][k]
                            m_move_info.append((nx, ny, nd, diff))
                            m_arr[r][c][k] = 0
                            break

        for r, c, d, diff in m_move_info:
            m_arr[r][c][d] += diff

        # 팩맨 이동
        max_cnt = -1
        pack_path_info = []
        for pm1 in range(4):
            for pm2 in range(4):
                for pm3 in range(4):
                    chk = set()
                    p_cnt = 0
                    move_list = [pm1, pm2, pm3]
                    path_info = []
                    px, py = R, C
                    for pmd in move_list:
                        # 다음 좌표
                        nx, ny = px + pdx[pmd], py + pdy[pmd]
                        if in_range(nx, ny):
                            if (nx, ny) not in chk:
                                p_cnt += sum(m_arr[nx][ny])
                            chk.add((nx, ny))
                            px, py = nx, ny
                            path_info.append((nx, ny))
                            continue

                        # 갈수없다면 break
                        break
                    if len(path_info) == 3:
                        # 최선이라면
                        if p_cnt > max_cnt:
                            max_cnt = p_cnt
                            pack_path_info = path_info[:]

        # 경로에 있는 몬스터 다 먹으면서 죽음 정보 갱신
        for ppx, ppy in pack_path_info:
            flag = False
            for k in range(8):
                if m_arr[ppx][ppy][k] != 0:
                    flag = True
                    m_arr[ppx][ppy][k] = 0
            if flag:
                die_arr[ppx][ppy] = turn + 2

        # 팩 맨 위치 이동
        if len(pack_path_info) > 0:
            R, C = pack_path_info[-1]

        # 몬스터 부화
        for r, c, d, diff in m_copy_info:
            m_arr[r][c][d] += diff

    ans = 0
    for i in range(1, 5):
        for j in range(1, 5):
            for k in range(8):
                ans += m_arr[i][j][k]

    print(ans)


main()