728x90
반응형
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
1번부터 번까지 명의 산타들이 크리스마스 이브를 준비하던 중, 산타의 주요 수송수단인 루돌프가 반란을 일으켰습니다. 루돌프는 산타들을 박치기하여 산타의 선물 배달을 방해하려고 합니다. 산타들은 루돌프를 잡아서 크리스마스를 구해야 합니다!
(1) 게임판의 구성
- 게임판은 크기의 격자로 이루어져 있습니다. 각 위치는 의 형태로 표현되며, 아래로 갈수록 이 증가, 오른쪽으로 갈수록 가 증가합니다. 좌상단은 입니다.
- 게임은 총 개의 턴에 걸쳐 진행되며 매 턴마다 루돌프와 산타들이 한 번씩 움직입니다. 루돌프가 한 번 움직인 뒤, 1번 산타부터 번 산타까지 순서대로 움직이게 됩니다. 이때 기절해있거나 격자 밖으로 빠져나가 게임에서 탈락한 산타들은 움직일 수 없습니다.
- 게임판에서 두 칸 , 사이의 거리는 으로 계산됩니다.
(2) 루돌프의 움직임
- 루돌프는 가장 가까운 산타를 향해 1칸 돌진합니다. 단, 게임에서 탈락하지 않은 산타 중 가장 가까운 산타를 선택해야 합니다.
- 만약 가장 가까운 산타가 2명 이상이라면, 좌표가 큰 산타를 향해 돌진합니다. 이 동일한 경우, 좌표가 큰 산타를 향해 돌진합니다.
- 루돌프는 상하좌우, 대각선을 포함한 인접한 8방향 중 하나로 돌진할 수 있습니다. (편의상 인접한 대각선 방향으로 전진하는 것도 1칸 전진하는 것이라 생각합니다.) 가장 우선순위가 높은 산타를 향해 8방향 중 가장 가까워지는 방향으로 한 칸 돌진합니다.
(3) 산타의 움직임
- 산타는 1번부터 번까지 순서대로 움직입니다.
- 기절했거나 이미 게임에서 탈락한 산타는 움직일 수 없습니다.
- 산타는 루돌프에게 거리가 가장 가까워지는 방향으로 1칸 이동합니다.
- 산타는 다른 산타가 있는 칸이나 게임판 밖으로는 움직일 수 없습니다.
- 움직일 수 있는 칸이 없다면 산타는 움직이지 않습니다.
- 움직일 수 있는 칸이 있더라도 만약 루돌프로부터 가까워질 수 있는 방법이 없다면 산타는 움직이지 않습니다.
- 산타는 상하좌우로 인접한 4방향 중 한 곳으로 움직일 수 있습니다. 이때 가장 가까워질 수 있는 방향이 여러 개라면, 상우하좌 우선순위에 맞춰 움직입니다.
(4) 충돌
- 산타와 루돌프가 같은 칸에 있게 되면 충돌이 발생합니다.
- 루돌프가 움직여서 충돌이 일어난 경우, 해당 산타는 만큼의 점수를 얻게 됩니다. 이와 동시에 산타는 루돌프가 이동해온 방향으로 칸 만큼 밀려나게 됩니다.
- 산타가 움직여서 충돌이 일어난 경우, 해당 산타는 만큼의 점수를 얻게 됩니다. 이와 동시에 산타는 자신이 이동해온 반대 방향으로 칸 만큼 밀려나게 됩니다.
- 밀려나는 것은 포물선 모양을 그리며 밀려나는 것이기 때문에 이동하는 도중에 충돌이 일어나지는 않고 정확히 원하는 위치에 도달하게 됩니다.
- 만약 밀려난 위치가 게임판 밖이라면 산타는 게임에서 탈락됩니다.
- 만약 밀려난 칸에 다른 산타가 있는 경우 상호작용이 발생합니다.
(5) 상호작용
- 루돌프와의 충돌 후 산타는 포물선의 궤적으로 이동하여 착지하게 되는 칸에서만 상호작용이 발생할 수 있습니다.
- 산타는 충돌 후 착지하게 되는 칸에 다른 산타가 있다면 그 산타는 1칸 해당 방향으로 밀려나게 됩니다. 그 옆에 산타가 있다면 연쇄적으로 1칸씩 밀려나는 것을 반복하게 됩니다. 게임판 밖으로 밀려나오게 된 산타의 경우 게임에서 탈락됩니다.
(6) 기절
- 산타는 루돌프와의 충돌 후 기절을 하게 됩니다. 현재가 번째 턴이었다면, 번째 턴까지 기절하게 되어 번째 턴부터 다시 정상상태가 됩니다.
- 기절한 산타는 움직일 수 없게 됩니다.
- 루돌프는 기절한 산타를 돌진 대상으로 선택할 수 있습니다.
(7) 게임 종료
- 번의 턴에 걸쳐 루돌프, 산타가 순서대로 움직인 이후 게임이 종료됩니다.
- 만약 명의 산타가 모두 게임에서 탈락하게 된다면 그 즉시 게임이 종료됩니다.
- 매 턴 이후 아직 탈락하지 않은 산타들에게는 1점씩을 추가로 부여합니다.
게임이 끝났을 때 각 산타가 얻은 최종 점수를 구하는 프로그램을 작성해보세요.
파이썬 풀이
from collections import deque
n, m, p, C, d = map(int, input().split())
Sx, Sy = map(int, input().split())
rx, ry = Sx-1, Sy-1
S = []
graph = [[0]*n for _ in range(n)]
graph[rx][ry] = -1
stun_santa = [0]*(p+1)
alive_santa = [1]*(p+1)
alive_santa[0] = 0
score = [0]*(p+1)
for _ in range(p):
a, b, c = map(int, input().split())
a, b, c = a, b-1, c-1
S.append((a, b, c))
graph[b][c] = a
# 루돌프와 가장 가까운 산타 찾기
def rudolf_most_near(x, y):
Q = deque()
Q.append((x, y))
dx = [1, -1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, 1, -1, 1, -1, 1, -1]
visit = [[0]*n for _ in range(n)]
visit[x][y] = 1
distance = [[0]*n for _ in range(n)]
temp = []
sx, sy = x, y
while Q:
x, y = Q.popleft()
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0:
visit[nx][ny] = 1
distance[nx][ny] = distance[x][y] + 1
if graph[nx][ny] == 0:
Q.append((nx, ny))
if graph[nx][ny] > 0:
temp.append((nx, ny, abs(sx-nx)**2 + abs(sy-ny)**2))
return sorted(temp, key=lambda x:(-x[2], x[0], x[1]))
# 루돌프 움직이기
def rudolf_move(x, y, ex, ey):
Q = deque()
Q.append((x, y))
dx = [1, -1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, 1, -1, 1, -1, 1, -1]
visit = [[0]*n for _ in range(n)]
visit[x][y] = 1
distance = [[0]*n for _ in range(n)]
temp = []
sx, sy = x, y
while Q:
x, y = Q.popleft()
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0:
temp.append((nx, ny, abs(nx-ex)**2 + abs(ny-ey)**2, dx[i], dy[i]))
return sorted(temp, key=lambda x:(-x[2], x[0], x[1]))
#산타 움직이기
def santa_move(number, x, y, ex, ey):
Q = deque()
Q.append((x, y))
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
distance = abs(x-ex)**2 + abs(y-ey)**2
temp = []
while Q:
x, y = Q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
dist = abs(nx-ex)**2 + abs(ny-ey)**2
if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] <= 0 and dist < distance:
distance = dist
temp.append((nx, ny, abs(ex-nx)**2 + abs(ey-ny)**2, dx[i], dy[i]))
return sorted(temp, key=lambda x:(-x[2]))
# 산타가 움직여서 루돌프랑 충돌
def santa_hit_rudolf(number, x, y, dx, dy):
nx = x + (dx*d)
ny = y + (dy*d)
if 0 <= nx < n and 0 <= ny < n:
if graph[nx][ny] == 0:
graph[nx][ny] = number
elif graph[nx][ny] > 0:
santa_hit_santa(nx, ny, dx, dy, graph[nx][ny])
graph[nx][ny] = number
return
else:
alive_santa[number] = 0
return
# 산타가 날아가는데 산타랑 충돌
def santa_hit_santa(x, y, dx, dy, post_value):
Q = deque()
Q.append((x, y, post_value))
while Q:
x, y, value = Q.popleft()
nx = x + dx
ny = y + dy
if 0 <= nx < n and 0 <= ny < n:
if graph[nx][ny] == 0:
graph[nx][ny] = value
else:
Q.append((nx, ny, graph[nx][ny]))
graph[nx][ny] = value
else:
alive_santa[value] = 0
# 루돌프가 움직여서 충돌
def rudolf_hit(x, y, dx, dy, number):
nx = x + dx*C
ny = y + dy*C
if 0 <= nx < n and 0 <= ny < n:
if graph[nx][ny] == 0:
graph[nx][ny] = graph[x][y]
else:
santa_hit_santa(nx, ny, dx, dy, graph[nx][ny])
graph[nx][ny] = graph[x][y]
else:
alive_santa[number] = 0
time = 0
for T in range(m):
if sum(alive_santa) == 0:
break
time += 1
# 루돌프 위치 찾기
most_near_santa = rudolf_most_near(rx, ry)
ex, ey, dist = most_near_santa.pop()
graph[rx][ry] = 0
# 루돌프 움직이기
rudolf_movement = rudolf_move(rx, ry, ex, ey)
rx, ry, rdist, dx, dy = rudolf_movement.pop()
# 만약 루돌프가 산타와 부딪히면
if graph[rx][ry] > 0:
stun_santa[graph[rx][ry]] = 2
score[graph[rx][ry]] += C
rudolf_hit(rx, ry, dx, dy, graph[rx][ry])
graph[rx][ry] = -1
S = []
for i in range(n):
for j in range(n):
if graph[i][j] > 0:
S.append((graph[i][j], i, j))
S.sort(key=lambda x:x[0])
for z in range(1, p+1):
santax, santay = -1, -1
for i in range(n):
for j in range(n):
if graph[i][j] == z:
santax, santay = i, j
# 만약 해당 루돌프가 존재하지 않으면
if santax == -1 and santay == -1:
continue
number = graph[santax][santay]
if stun_santa[number] != 0:
continue
santa_movement = santa_move(number, santax, santay, rx, ry)
if len(santa_movement) == 0:
continue
graph[santax][santay] = 0
sx, sy, dist, dx, dy = santa_movement.pop()
if graph[sx][sy] == 0:
graph[sx][sy] = number
elif graph[sx][sy] == -1:
score[number] += d
stun_santa[number] = 2
santa_hit_rudolf(number, sx, sy, -dx, -dy)
for i in range(1, p+1):
if alive_santa[i] == 1:
score[i] += 1
for i in range(1, p+1):
if stun_santa[i] > 0:
stun_santa[i] -= 1
print(*score[1:])728x90
반응형
'코딩테스트 준비' 카테고리의 다른 글
| [코드트리] - 나무 박멸 파이썬 풀이 (0) | 2024.03.31 |
|---|---|
| 코드트리 - 예술성 (0) | 2023.10.10 |
| 코드트리 - 코드트리 빵 (파이썬, Python) (0) | 2023.10.09 |