본문 바로가기

알고리즘 문제풀이/코드트리(삼성 기출)

팩맨(2021 하반기 오후 1번, 백준 23290 마법사 상어와 복제)

문제 링크: https://www.codetree.ai/frequent-problems//pacman

 

코드트리

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

*같은 문제: 백준 23290 - 마법사 상어와 복제

 

빡구현 문제. 매 스텝마다 (몬스터 복제 - 몬스터 이동 - 팩맨 이동 - 시체 유지시간 감소 - 복제 완료) 사이클이 반복된다.

 

팩맨은 알을 제거하지 않고 오직 해당 시점에 존재하는 몬스터만 제거하기 때문에, 복제/이동을 수행하는 함수에서 이동 결과를 tmp라는 배열에 따로 저장해두고, tmp의 상태만을 가지고 팩맨이 이동하도록 결정했다. 

 

팩맨의 이동 우선순위는 상>하>좌>우인데, 우우우->상상상 방향으로 탐색하여 최종 방향을 정했다. 현재 스텝의 살아남은 몬스터 + 현재 스텝에서 만든 알이 그대로 다음 스텝의 초기 몬스터 상태가 되기 때문에 마지막에 tmp 결과를 그대로 field 결과에 합쳐줬다.

 

def mon_copy_move(field):
tmp = [[[] for _ in range(5)] for _ in range(5)]
for y in range(1, 5):
for x in range(1, 5):
mon_lst = field[y][x][0]
for mon in mon_lst:
d = mon-1
move_flag = False
for i in range(8):
d = (d+1)%8
new_y, new_x = y+mon_dir[d][0], x+mon_dir[d][1]
if (0 < new_y <= 4 and 0 < new_x <= 4) and not(new_y == r and new_x == c) and field[new_y][new_x][1]==0: # 이동 가능하면
tmp[new_y][new_x].append(d)
move_flag = True
break
# 격자 바깥이거나, 팩맨이 있거나, 시체가 있다면 다음 방향
if not move_flag: # 못 움직임
tmp[y][x].append((d+1)%8) # 원래 방향 유지한 채로 원래 위치
return tmp # 이동한 결과 return
def pac_move_del_mon(field, tmp, r, c):
dir = [0, 0, 0] # 우선순위 가장 낮은 방향부터 탐색
max_del = 0
for i in range(4):
one_y, one_x = r+pac_dir[i][0], c+pac_dir[i][1]
if 0 < one_y <= 4 and 0 < one_x <= 4:
for j in range(4):
two_y, two_x = one_y+pac_dir[j][0], one_x+pac_dir[j][1]
if 0 < two_y <= 4 and 0 < two_x <= 4:
for k in range(4):
thr_y, thr_x = two_y+pac_dir[k][0], two_x+pac_dir[k][1]
if 0 < thr_y <= 4 and 0 < thr_x <= 4: # 해당 방향으로 이동할 수 있다면 삭제할 몬스터 수 체크
cur_del = len(tmp[one_y][one_x])
if not(r == two_y and c == two_x): # 이동 위치가 안 겹치면
cur_del += len(tmp[two_y][two_x])
if not(one_y == thr_y and one_x == thr_x): # 이동 위치가 안 겹치면
cur_del += len(tmp[thr_y][thr_x])
if max_del <= cur_del: # 삭제하는 몬스터 수 같으면 나중에 탐색하는 방향이 우선순위 높음
max_del = cur_del
dir = [i, j, k]
one_y, one_x = r+pac_dir[dir[0]][0], c+pac_dir[dir[0]][1]
two_y, two_x = one_y+pac_dir[dir[1]][0], one_x+pac_dir[dir[1]][1]
thr_y, thr_x = two_y+pac_dir[dir[2]][0], two_x+pac_dir[dir[2]][1]
# 시체 사라지는 시간 업데이트, 이 함수 바로 다음에 1 빼는 함수 호출
if tmp[one_y][one_x]: field[one_y][one_x][1] = 3
if tmp[two_y][two_x]: field[two_y][two_x][1] = 3
if tmp[thr_y][thr_x]: field[thr_y][thr_x][1] = 3
tmp[one_y][one_x], tmp[two_y][two_x], tmp[thr_y][thr_x] = [], [], [] # 최종 이동 방향에 있는 몬스터 제거
return field, tmp, thr_y, thr_x # 살아남은 몬스터와 팩맨 이동 위치 반환
def corpse_reduce(field):
for y in range(1, 5):
for x in range(1, 5):
if field[y][x][1] > 0:
field[y][x][1] -= 1
return field
def hatch(field, tmp):
# 팩맨은 알 삭제 안함
# 팩맨 이동과 상관 없이, 현재 위치의 이번 턴 초기 몬스터 + 현재 위치로 이동하고 살아남은 몬스터가 다음 턴 초기 몬스터가 됨
for y in range(1, 5):
for x in range(1, 5):
field[y][x][0] += tmp[y][x]
return field
if __name__ == "__main__":
field = [[[[], 0] for _ in range(5)] for _ in range(5)]
# 각 칸마다 몬스터/알, 시체 사라지는 시간 저장
m, t = map(int, input().split())
r, c = map(int, input().split())
pac_dir = [[0,1], [1,0], [0,-1], [-1,0]] # 우하좌상 - 우선순위 가장 낮은 방향부터
mon_dir = [[-1,0], [-1,-1], [0,-1], [1,-1], [1,0], [1,1], [0,1], [-1,1]] #0: 북, 1: 서북..., 코드트리용
# mon_dir = [[0,-1], [-1,-1], [-1,0], [-1,1], [0,1], [1,1], [1,0], [1,-1]] #0: 서, 1: 서북..., 백준용
for _ in range(m):
y, x, d = map(int, input().split())
field[y][x][0].append(d-1)
for _ in range(t):
tmp = mon_copy_move(field) # 몬스터 복제 및 이동
field, tmp, r, c = pac_move_del_mon(field, tmp, r, c) # 팩맨 이동 및 경로 내 몬스터 삭제
field = corpse_reduce(field) # 시체 유지 시간 감소
field = hatch(field, tmp) # 복제 완료
sol = 0
for y in range(1, 5):
for x in range(1, 5):
sol += len(field[y][x][0])
print(sol)
view raw 팩맨.py hosted with ❤ by GitHub