문제 링크: https://www.codetree.ai/frequent-problems//pacman
코드트리
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
*같은 문제: 백준 23290 - 마법사 상어와 복제
빡구현 문제. 매 스텝마다 (몬스터 복제 - 몬스터 이동 - 팩맨 이동 - 시체 유지시간 감소 - 복제 완료) 사이클이 반복된다.
팩맨은 알을 제거하지 않고 오직 해당 시점에 존재하는 몬스터만 제거하기 때문에, 복제/이동을 수행하는 함수에서 이동 결과를 tmp라는 배열에 따로 저장해두고, tmp의 상태만을 가지고 팩맨이 이동하도록 결정했다.
팩맨의 이동 우선순위는 상>하>좌>우인데, 우우우->상상상 방향으로 탐색하여 최종 방향을 정했다. 현재 스텝의 살아남은 몬스터 + 현재 스텝에서 만든 알이 그대로 다음 스텝의 초기 몬스터 상태가 되기 때문에 마지막에 tmp 결과를 그대로 field 결과에 합쳐줬다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
'알고리즘 문제풀이 > 코드트리(삼성 기출)' 카테고리의 다른 글
연산자 배치하기(2017 하반기 오후 2번, 백준 14888 연산자 끼워넣기) (0) | 2022.10.08 |
---|---|
냉방 시스템(2021 하반기 오전 2번, 백준 23289 온풍기 안녕!) (0) | 2022.10.08 |
Sam의 피자학교(2021 하반기 오후 2번, 백준 23291 어항 정리) (0) | 2022.10.08 |
예술성(2022 상반기 오전 2번) (0) | 2022.10.07 |
나무박멸(2022 상반기 오후 2번) (0) | 2022.10.07 |