[코테준비] 삼성15. 코드트리: 팩맨 python

근데 글쓰기에 앞서 이상한 점이 있다. 별로 풀이가 없는 문제에 대한 글을 내가 썼는데, 왜 제목을 똑같이 검색해도 안 뜨는 것일까..? 뭔가 검색 금지로 되어있는 건 아닌지.. 근데 딱히 그런 건 없어 보이는데.. 하여간 의문이다. 그냥 방문자수가 적어서 그런가.. 🥲

---

팩맨

• 링크: https://www.codetree.ai/training-field/frequent-problems/problems/pacman/description
• 기출: 삼성 SW 역량테스트 2021 하반기 오후 1번 문제
• 난이도:골드 1
• 분류: 시뮬레이션
• 직접 푼 여부: O  무려 하루종일 걸림 10시간동안 푼 듯..
• 언어: 파이썬

풀이 노트

원래 코딩 공부를 할 때, 특히 코테를 앞두고 있을 때 문제를 끌어안고 있는 것은 효율적이지 못하지만, 정말 이 코드에 문제가 없는 것 같아서 찾아내고야 말겠다는 집념으로 아침부터 밤 11시까지 끌어안고 있었다. 약간 미련했던 것 같기도 하지만, 뿌듯하다. 

아래는 문제를 풀며 정리한 노트이다. 이 문제 역시 사용할 definition들을 먼저 생각하고 코딩하였다. 그래서 이렇게 오래 걸렸던 이유는 빨간색 글씨로 쓴 2번과 3번 때문이다. 

 

아래 코드에 상세한 설명을 달아놓았으니, 이를 보면 이해가 될 것이다! 

 

그래서 나를 애 먹였던 포인트는 다음과 같다. 

1. 팩맨이 한 세트에서 이동할 때 갔던 곳도 갈 수 있다는 것! + 출발에 있던 몬스터는 먹지 않고 시작하는 것! 대신 다른 곳에 갔다가 출발점에 오면 그곳에 있는 몬스터는 먹을 수 있다
2. visited로 팩맨의 이동을 관리하였다 (갔던 곳을 다시 갈 수는 있지만, 몬스터를 다시 먹지는 않으니까). 그런데, True False로 갔다가 return 되면 false로 바꾸었다. 이렇게 하니, "1 지역-2 지역-1지역" 순으로 이동하고 마지막 1지역에서 나왔을 때 (" 1지역-2지역 ") 1번을 방문하지 않은 것으로 된다는 것이다. 그래서 2차원 배열로 T/F 관리하지 않고 visited = [] list로 만들어서 append와 remove를 해주었다. 

 

정답 코드 💻

# 팩맨 - 코드트리
import copy
import sys
input = sys.stdin.readline


# prepare --------------------
def int_minusone(x):
    """input용 def: 좌표값 1부터 시작하니까 0으로 맞춰줌"""
    return int(x)-1

# pacman 이동 - 상-좌-하-우
dr = [-1, 0,1, 0]
dc = [0,-1, 0, 1]

# monster의 이동
monmove = [[-1,0], [-1,-1],[0,-1], [1,-1], [1,0],[1,1],[0,1],[-1,1]]

# 격자에서 몬스터 위치 및 direction [[ [] [] [] []], [ [] [] [] [] ], ... ]
monster = [ [[] for _ in range(4)] for _ in range(4)] # 몬스터 방향
egg =[ [[] for _ in range(4)] for _ in range(4)] # 알 방향
dead = [[[] for _ in range(4)] for _ in range(4)] # 시체 남은 시간


# input --------------------
m,t = map(int,input().split()) # m: monster 초기 수, t: 몇회 반복
pacman = tuple(map(int_minusone, input().split()))  # 팩맨 위치(r,c)
for _ in range(m):
    r,c,d = map(int_minusone,input().split())
    monster[r][c].append(d)

# monster egg & move --------------------
def mon_egg_move():
    global monster, egg
    # 1) 현재 몬스터의 방향과 같은 알 생성 - 즉, 복사
    egg=copy.deepcopy(monster)
    # 2) monster 이동
    tempmonster = copy.deepcopy(monster)
    monster = [ [[] for _ in range(4)] for _ in range(4)]
    for i in range(4):
        for j in range(4):
            while tempmonster[i][j]:
                skip = False
                # 해당 위치에 몬스터가 있으면
                now=tempmonster[i][j].pop()# 현재 방향
                for drc in range(8):
                    nowindec = (now+drc)%8 # 돌아볼 방향 (처음엔 0이니까 now와 동일)
                    newr, newc= i+ monmove[nowindec][0], j+monmove[nowindec][1] # 이동할 위치
                    # 이동가능한지 check 1)범위 2)pacman 없음 3) 시체 없음
                    if 0<=newr<4 and 0<=newc<4 and (newr,newc) != pacman and len(dead[newr][newc]) ==0:
                        monster[newr][newc].append(nowindec)
                        skip = True
                        break # 이동했으면 끝
                # 8방향다 이동 못했으면, 원래 위치 원래 방향
                if not skip:
                    monster[i][j].append(now)


# pacman move --------------------
def pacman_move(level, eat, r,c, path):
    """팩맨 이동"""
    # 1. 젤 많이 잡아 먹는 루트로 이동 -> 루트 찾기
    # 2. 먹힌 몬스터들 시체 표시 (3로)

    # level: 몇번 이동
    # eat: 지금까지 먹은 양 - 초기값=monster[r][c]
    # r,c: 현재 팩맨 위치  - 초기값 = pacman
    # path: list 지금까지 움직인 좌표값 - 초기값 =[(r,c)]
    global total_eat, visited, pacman, maxpath, monster, dead
    if level ==3: # 1. 3번 이동했을 때, 젤 많이 먹는 루트로 이동
        if eat > total_eat: # = 을 안포함해야 상좌하우 우선순위대로 됨
            total_eat=eat
            maxpath = copy.deepcopy(path)
            pacman = (r, c) # 팩맨 위치 업데이트
        return
    for i in range(4):
        newr, newc = r+dr[i], c+dc[i]
        if 0<=newr<4 and 0<=newc<4 :
            plus =0
            if not (newr, newc) in visited:
                # 갔던 곳 또 가도 되는데, 대신 몬스터는 이미 먹었으니 또 못먹음
                plus = len(monster[newr][newc])
            visited.append((newr, newc))
            path.append((newr, newc))
            pacman_move(level+1, eat +plus, newr, newc, path)
            path.remove((newr, newc))
            visited.remove((newr, newc))

    return

# 죽은 몬스터 체크 --------------------
def markdead():
    global  dead
    for r,c in maxpath:
        if len(monster[r][c])>0: dead[r][c].append(3) # path에 몬스터가 있으면, 죽으니까  3으로 표시
        monster[r][c] = [] # 몬스터 죽음 - 없어짐
# dead & egg hatch --------------------
def mon_disappear_egg_hatch():
    """시체 처리 & 알 부하"""
    # 죽은 몬스터 시체 없애기: 3-> 2 (방금 생김), 2->1   / 1-> remove
    # 알 부하 : 알 -> monster map에 추가 ""
    global monster, egg, dead
    tempdead = copy.deepcopy(dead)
    dead = [[[] for _ in range(4)] for _ in range(4)]
    for i in range(4):
        for j in range(4):
            # dead 처리
            if 3 in tempdead[i][j]: dead[i][j].append(2)
            if 2 in tempdead[i][j]: dead[i][j].append(1)
            # 알 부화
            monster[i][j].extend(egg[i][j])


# main  --------------------
# 1) 작업
for tt in range(t):
    mon_egg_move() # 1) 알 생성, 움직임
    # pacman 이동
    r,c = pacman
    total_eat = -1  # 0개 먹는 경우에도 업데이트 되어야 함
    visited = []
    maxpath = []
    pacman_move(0, 0, r,c, []) # 2) 팩맨 움직이며 먹음
    markdead()
    mon_disappear_egg_hatch() # 3) 시체 처리 & 알 -> monster
# 2) 답 구하기
answer =0 # 남아있는 몬스터 수
for i in range(4):
    for j in range(4):
        answer += len(monster[i][j])
print(answer)

 

정답!

수많은 테케 도전들의 흔적