코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
문제종류
bfs, dx dy technique, simulation
풀이시간
설계 30분 구현 50분
풀이방법
1. 대상자 선정
문제에서 요구하는 공격 대상자와, 공격자를 구할때의 정렬 조건은 정반대입니다.
따라서 각 좌표의 공격, 최근 공격정보, 행 + 열, 열 정보를 모두 하나의 배열에 넣고
공격자, 대상자 = sorted(arr)[0], sorted(arr)[-1] 로 대상을 구하면됩니다.
공격자와 대상자가 같은 경우는 살아있는 포탑이 하나일경우 로직이 수행될 수 없으므로 불가능합니다.
2. 레이저 공격
공격자가 우 하 좌 상 순서의 움직임으로 대상에 도달할 수 있으면 레이저 공격을 할 수 있습니다.
대상자에서 공격자에 도달하는 bfs 를 수행후
공격자에서 대상자로 가는 최단 경로를 저장합니다.
3. 포탄 공격
레이저 공격을 할 수 없을 경우, 즉 공격자의 상 하 좌 우 인접한 칸에 갈 수 없는 경우 수행합니다.
대상자의 8방향을 탐색하며 포탄 공격을 수행합니다. (공격자는 대상이 될 수 없는 것에 주의합니다.)
코드
from collections import deque
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
bx, by = [-1, -1, -1, 0, 0, 1, 1, 1], [-1, 0, 1, -1, 1, -1, 0, 1]
INF = 987654321
def transpose(nx, ny, n, m):
nx = n - 1 if nx < 0 else nx % n
ny = m - 1 if ny < 0 else ny % m
return nx, ny
def main():
n, m, k = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(n)]
# 초기화 값
EMPTY = (0, 0)
# (공격력, 가장 최근 공격 저장)
tower = [[EMPTY] * m for i in range(n)]
for r in range(n):
for c in range(m):
tower[r][c] = (arr[r][c], 0)
for turn in range(1, k + 1):
# 살아있는 포탑이 1개면 종료
live_cnt = 0
for x in range(n):
for y in range(m):
if tower[x][y][0] > 0:
live_cnt += 1
if live_cnt == 1:
break
attack_tmp = []
for x in range(n):
for y in range(m):
# 이미 부서진 곳 후보에 넣지 않음
if tower[x][y][0] != 0:
attack_tmp.append((*tower[x][y], x + y, y))
# 영향 받은 좌표 저장
hist = set()
# 공격자 선정
attacker = sorted(attack_tmp, key=lambda att: (att[0], -att[1], -att[2], -att[3]))[0]
# 대상자 선정
defender = sorted(attack_tmp, key=lambda att: (att[0], -att[1], -att[2], -att[3]))[-1]
ax, ay = attacker[2] - attacker[3], attacker[3]
hist.add((ax, ay))
dfx, dfy = defender[2] - defender[3], defender[3]
# 공격자 공격력 증가
tower[ax][ay] = (tower[ax][ay][0] + n + m, turn)
# 레이저 공격 판단
rtmp = [[INF] * m for _ in range(n)]
# bfs 수행 공격 대상 => 공격자 벽 통과 불가 => 한번 갔던 곳 더가기 불가
q = deque([])
q.append((dfx, dfy, 0))
while len(q):
fx, fy, fc = q.popleft()
# 방문한곳이면 못감
if rtmp[fx][fy] != INF:
continue
rtmp[fx][fy] = fc
for ddx, ddy in zip(dx, dy):
nx, ny = fx + ddx, fy + ddy
nx, ny = transpose(nx, ny, n, m)
if rtmp[nx][ny] != INF or tower[nx][ny][0] == 0:
continue
q.append((nx, ny, fc + 1))
min_dist = INF
for ddx, ddy in zip(dx, dy):
nx, ny = ax + ddx, ay + ddy
nx, ny = transpose(nx, ny, n, m)
min_dist = min(min_dist, rtmp[nx][ny])
# 레이저 공격 수행
if min_dist != INF:
rpath = []
cx, cy = ax, ay
for rp in range(min_dist + 1):
cmd = INF
for ddx, ddy in zip(dx, dy):
nx, ny = cx + ddx, cy + ddy
nx, ny = transpose(nx, ny, n, m)
cmd = min(cmd, rtmp[nx][ny])
# 우 하 좌 상으로 탐색하며
for ddx, ddy in zip(dx, dy):
nx, ny = cx + ddx, cy + ddy
nx, ny = transpose(nx, ny, n, m)
if rtmp[nx][ny] == cmd:
rpath.append((nx, ny))
cx, cy = nx, ny
break
# 레이저 공격 수행 (영향 범위에 추가)
dam = tower[ax][ay][0]
for ri, (rx, ry) in enumerate(rpath):
t_dam = dam // 2
if ri == len(rpath) - 1:
t_dam = dam
tower[rx][ry] = (max(0, tower[rx][ry][0] - t_dam), tower[rx][ry][1])
hist.add((rx, ry))
# 포탄 공격 수행
else:
dam = tower[ax][ay][0]
# 타켓 즉시 공격후 추가
tower[dfx][dfy] = (max(0, tower[dfx][dfy][0] - dam), tower[dfx][dfy][1])
hist.add((dfx, dfy))
for bbx, bby in zip(bx, by):
nx, ny = dfx + bbx, dfy + bby
nx, ny = transpose(nx, ny, n, m)
# 이미 부서진 곳이 아니고, 공격자가 아닐경우
if tower[nx][ny][0] != 0 and (nx, ny) != (ax, ay):
tower[nx][ny] = (max(0, tower[nx][ny][0] - dam // 2), tower[nx][ny][1])
hist.add((nx, ny))
# 포탑 정비
for x in range(n):
for y in range(m):
if tower[x][y][0] != 0 and (x, y) not in hist:
tower[x][y] = (tower[x][y][0] + 1, tower[x][y][1])
# turn 끝난이후
ans = 0
for r in range(n):
for c in range(m):
ans = max(ans, tower[r][c][0])
print(ans)
main()
'알고리즘 > 코드트리' 카테고리의 다른 글
[코드트리] - 팩맨 (0) | 2023.09.27 |
---|---|
[코드트리] - 나무박멸 (1) | 2023.09.26 |
[코드트리] - 싸움땅 (0) | 2023.09.23 |
[코드트리] - 시공의 돌풍 (0) | 2023.09.23 |
[코드트리] - 격자 숫자 놀이 (0) | 2023.09.22 |