메두사와 전사들
Simulation, BFS
평균 : 180'
sol : -
- 수행 시간 : -
- 메모리 : -
New Skills
BFS를 더 자유롭게 쓸 수 있다는 걸 깨달았다.
[모범 답안]
import sys
from collections import deque
# 방향 우선순위
P1 = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우
P2 = [(0, -1), (0, 1), (-1, 0), (1, 0)] # 좌우상하
# 시야(90도) 3갈래: 위/아래/좌/우
VISION_DXYS = [
[(-1, -1), (-1, 0), (-1, 1)], # 위
[(1, -1), (1, 0), (1, 1)], # 아래
[(-1, -1), (0, -1), (1, -1)], # 좌
[(-1, 1), (0, 1), (1, 1)], # 우
]
def in_range(x, y, N):
return 0 <= x < N and 0 <= y < N
def manhattan(ax, ay, bx, by):
return abs(ax - bx) + abs(ay - by)
class WarriorMap:
"""전사 배열 + 칸별 전사 인덱스 집합. pop-back swap 로 O(1) 삭제 지향."""
__slots__ = ("N", "warriors", "cells")
def __init__(self, N, init_warriors):
self.N = N
self.warriors = list(init_warriors) # [(x,y), ...]
self.cells = [[set() for _ in range(N)] for __ in range(N)]
for i, (x, y) in enumerate(self.warriors):
self.cells[x][y].add(i)
def _erase_index_from_cell(self, idx):
x, y = self.warriors[idx]
self.cells[x][y].discard(idx)
def _add_index_to_cell(self, idx):
x, y = self.warriors[idx]
self.cells[x][y].add(idx)
def remove_warrior(self, idx):
"""인덱스 전사 제거: 마지막과 스왑 후 pop."""
self._erase_index_from_cell(idx)
last = len(self.warriors) - 1
if idx != last:
# 스왑
self.warriors[idx] = self.warriors[last]
# 셀의 집합에서 last 인덱스를 없애고 idx로 바꿈
x, y = self.warriors[idx]
self.cells[x][y].discard(last)
self.cells[x][y].add(idx)
self.warriors.pop()
def remove_same_cell(self, mx, my):
"""메두사와 같은 칸 전사 모두 제거. 제거 수 반환."""
removed = 0
i = 0
while i < len(self.warriors):
if self.warriors[i][0] == mx and self.warriors[i][1] == my:
self.remove_warrior(i)
removed += 1
else:
i += 1
return removed
def is_warrior_at(self, x, y):
return len(self.cells[x][y]) > 0
def move_warrior_once(self, idx, mx, my, vision_map, pri):
"""전사 idx를 pri 우선순위로 1칸 이동 시도. 성공 시 1, 아니면 0."""
x, y = self.warriors[idx]
d0 = manhattan(x, y, mx, my)
N = self.N
for dx, dy in pri:
nx, ny = x + dx, y + dy
if not in_range(nx, ny, N):
continue
if vision_map[nx][ny] == 1: # 시야로는 이동 불가
continue
if manhattan(nx, ny, mx, my) < d0:
# 셀 집합에서 인덱스 이동
self.cells[x][y].discard(idx)
self.warriors[idx] = (nx, ny)
self.cells[nx][ny].add(idx)
return 1
return 0
def warriors_move(self, vision_map, mx, my):
"""석화되지 않은 전사들의 이동(최대 2칸); (총 이동 칸수, 공격자 수)"""
# 메두사와 같은 칸 전사 제거 (이들은 공격자 집계와 무관)
self.remove_same_cell(mx, my)
steps_sum = 0
# 이동 가능한 전사만 이동 (현재 위치가 시야 바깥)
i = 0
while i < len(self.warriors):
x, y = self.warriors[i]
if vision_map[x][y] == 0:
steps_sum += self.move_warrior_once(i, mx, my, vision_map, P1)
steps_sum += self.move_warrior_once(i, mx, my, vision_map, P2)
i += 1
# 이동 후 메두사와 같은 칸 전사 제거 → 공격자 수
attackers = self.remove_same_cell(mx, my)
return steps_sum, attackers
def get_vision_map(N, wmap: WarriorMap, mx, my, dxys3):
"""해당 방향의 시야 맵(1)과 시야에 보이는 전사 수 반환."""
vision = [[0]*N for _ in range(N)]
seen_cnt = 0
# 보인 전사(가림 시작점)
# type: 0(좌 대각), 1(직선), 2(우 대각)
vis_q = deque()
# 1) 표시 BFS: 3갈래로만 퍼뜨리며 시야 칠하기
q = deque()
q.append((mx, my))
while q:
x, y = q.popleft()
for dxi, dyi in dxys3:
nx, ny = x + dxi, y + dyi
if not in_range(nx, ny, N) or vision[nx][ny] == 1:
continue
# 전사를 처음 만났다면 갈래 타입 분류
if wmap.is_warrior_at(nx, ny):
if nx == mx or ny == my:
vis_q.append((nx, ny, 1))
else:
# dxys3[0]과 같은 부호면 좌, 아니면 우
t = 0 if (nx - mx) * dxys3[0][0] > 0 and (ny - my) * dxys3[0][1] > 0 else 2
vis_q.append((nx, ny, t))
vision[nx][ny] = 1
q.append((nx, ny))
# 2) 가림 BFS: 전사 뒤쪽(같은 갈래)을 0으로 지움
while vis_q:
x, y, t = vis_q.popleft()
for d, (dxi, dyi) in enumerate(dxys3):
if t == 1 and d != 1:
continue
if t == 0 and d == 2:
continue
if t == 2 and d == 0:
continue
nx, ny = x + dxi, y + dyi
if not in_range(nx, ny, N) or vision[nx][ny] == 0:
continue
vision[nx][ny] = 0
vis_q.append((nx, ny, t))
# 시야에 남은 칸의 전사 수(칸별 집합 크기 합)
for i in range(N):
row_cells = wmap.cells[i]
vrow = vision[i]
for j in range(N):
if vrow[j]:
seen_cnt += len(row_cells[j])
return vision, seen_cnt
def bfs_dist_from_target(road, ex, ey):
"""도로(0)만 통과, (ex,ey)에서 모든 칸까지 최단거리."""
N = len(road)
dist = [[-1]*N for _ in range(N)]
dq = deque()
dq.append((ex, ey))
dist[ex][ey] = 0
while dq:
x, y = dq.popleft()
for dx, dy in P1: # 상하좌우
nx, ny = x + dx, y + dy
if not in_range(nx, ny, N) or road[nx][ny] == 1 or dist[nx][ny] != -1:
continue
dist[nx][ny] = dist[x][y] + 1
dq.append((nx, ny))
return dist
def move_medusa_one(dist, x, y):
"""메두사를 1칸 이동(거리 감소 + 상/하/좌/우 우선). 이동 후 좌표 반환."""
N = len(dist)
for dx, dy in P1:
nx, ny = x + dx, y + dy
if in_range(nx, ny, N) and dist[nx][ny] != -1 and dist[nx][ny] < dist[x][y]:
return nx, ny
return x, y # 이동 불가 케이스는 문제상 발생하지 않음(경로 존재 가정)
def main():
it = iter(sys.stdin.buffer.read().split())
try:
N = int(next(it)); M = int(next(it))
except StopIteration:
return
sx = int(next(it)); sy = int(next(it)); ex = int(next(it)); ey = int(next(it))
init_warriors = []
for _ in range(M):
ax = int(next(it)); ay = int(next(it))
init_warriors.append((ax, ay))
road = [[0]*N for _ in range(N)]
for i in range(N):
for j in range(N):
road[i][j] = int(next(it))
dist = bfs_dist_from_target(road, ex, ey)
if dist[sx][sy] == -1:
print(-1)
return
wmap = WarriorMap(N, init_warriors)
mx, my = sx, sy
out_lines = []
while not (mx == ex and my == ey):
# [1] 메두사 이동
mx, my = move_medusa_one(dist, mx, my)
if mx == ex and my == ey:
out_lines.append("0")
break
# [2] 시야 방향 선택 (동률: 상/하/좌/우 유지)
best_seen = -1
best_vision = None
for d in range(4):
vision_map, seen = get_vision_map(N, wmap, mx, my, VISION_DXYS[d])
if seen > best_seen:
best_seen = seen
best_vision = vision_map
# [3] 전사 이동
steps_sum, attackers = wmap.warriors_move(best_vision, mx, my)
# [출력] 전사 총 이동칸 수, 석화 수(=best_seen), 공격자 수
out_lines.append(f"{steps_sum} {best_seen} {attackers}")
sys.stdout.write("\n".join(out_lines))
if __name__ == "__main__":
main()