1) BFS 경로 복원으로 메두사가 공원까지 도로를 따라 갈 수 있는 최단경로 복원하기
2) 전사 뒤 영역을 메두사가 보지 못한다고 -1로 두면 안되는 이유:
-1로 인해 볼 수 있는 전사(분홍 영역)를 탐색할 수 없게 되는 경우가 생김
-> 그래서 일단 전부 지나갈 수 있도록 해당 영역을 맵에서는 0으로 갱신하여 전사 뒤 영역도 탐색하게 한 다음, 0으로 갱신된(실제 메두사는 가려져서 못보는 영역) 좌표는 따로cant_look_sight에 저장하여medusa_sight(BFS로 탐색한 전체 영역) 에서 빼준 다음 최종 medusa_sight(메두사가 볼 수 있는 영역)를 리턴함
3) 맨해튼 거리로 거리 계산해야 함 ->dist = abs(nx - sr) + abs(ny - sc)
4) 전사 이동 시, 상하좌우 중 메두사와의 최소 거리인 방향으로 이동하는 게 아닌 "메두사와의 거리를 줄일 수 있는 방향" 인지도 꼭 체크해야 함! -> 기존 좌표의 메두사와의 거리(origin_dist)보다 더 작아지는 지도 체크
5) 방향 선택 기준의 우선순위는 각각 다르므로 주의하기
6) 돌이 된 전사는 이번 턴에서만 이동하지 못하는 것 -> 이번 턴 이동에서 돌 좌표만 제외하고 이동
7) 항상 인덱스, x, y 축 방향 주의
8) 조건 하나라도 놓치지 않기 -> 메두사가 이동한 좌표에 전사 있으면 즉시 없애기
9) 한 좌표 안에 전사 여러명 있을 수 있음 주의하기
10) 메두사 집에서 공원까지 가는 경로가 없을 수 있음 주의
11) 전사 이동 시 메두사 시야에 포함되지 않는 칸이여야 함not in medusa_s
from collections import deque
N, M = map(int, input().split())
sr, sc, er, ec = map(int, input().split())
line = list(map(int, input().split()))
attackers = []
for i in range(0, 2 * M, 2):
attackers.append((line[i], line[i + 1]))
# print(attackers)
maps = []
for i in range(N):
line = list(map(int, input().split()))
maps.append(line)
# print(maps)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 메두사가 공원까지 도로를 따라 갈 수 있는 최단경로 구하는 함수
def search_shortest_path():
visited = [[False] * N for _ in range(N)]
parents = [[None] * N for _ in range(N)]
visited[sr][sc] = True
q = deque()
q.append((sr, sc, 0))
while q:
x, y, level = q.popleft()
# 공원에 도달했다면 종료
if x == er and y == ec:
break
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and maps[nx][ny] == 0:
q.append((nx, ny, level + 1))
visited[nx][ny] = True
parents[nx][ny] = (x, y) # 부모 좌표 저장
# 최단 경로 복원 ----------------------------------------
path = [(er, ec)]
cur_x, cur_y = er, ec
while True:
if parents[cur_x][cur_y] != None:
cur_x, cur_y = parents[cur_x][cur_y]
path.append((cur_x, cur_y))
else:
break
path.reverse()
return path
shortest_path = search_shortest_path()
medusa_idx = 0
def count_attacker(d):
# 메두사가 볼 수 있는 영역 = 0, 못 보는 영역 = -1으로 표시
avail_maps = [[-1] * N for _ in range(N)]
if d == 0: # 상
for i in range(1, sr + 1):
nx = sr - i
avail_maps[nx][sc] = 0
# 메두사 기준 오른쪽
for j in range(1, i + 1):
ny = sc + j
if 0 <= ny < N:
avail_maps[nx][ny] = 0
# 메두사 기준 왼쪽
for j in range(1, i + 1):
ny = sc - j
if 0 <= ny < N:
avail_maps[nx][ny] = 0
elif d == 1: # 하
for i in range(1, N - sr):
nx = sr + i
avail_maps[nx][sc] = 0
# 메두사 기준 오른쪽
for j in range(1, i + 1):
ny = sc + j
if 0 <= ny < N:
avail_maps[nx][ny] = 0
# 메두사 기준 왼쪽
for j in range(1, i + 1):
ny = sc - j
if 0 <= ny < N:
avail_maps[nx][ny] = 0
elif d == 2: # 좌
for i in range(1, sc + 1):
ny = sc - i
avail_maps[sr][ny] = 0
# 메두사 기준 오른쪽
for j in range(1, i + 1):
nx = sr - j
if 0 <= nx < N:
avail_maps[nx][ny] = 0
# 메두사 기준 왼쪽
for j in range(1, i + 1):
nx = sr + j
if 0 <= nx < N:
avail_maps[nx][ny] = 0
elif d == 3: # 우
for i in range(1, N - sc):
ny = sc + i
avail_maps[sr][ny] = 0
# 메두사 기준 오른쪽
for j in range(1, i + 1):
nx = sr - j
if 0 <= nx < N:
avail_maps[nx][ny] = 0
# 메두사 기준 왼쪽
for j in range(1, i + 1):
nx = sr + j
if 0 <= nx < N:
avail_maps[nx][ny] = 0
# 메두사가 볼 수 있는 전사 수 카운트
q = deque()
q.append((sr, sc))
visited = [[False] * N for _ in range(N)]
# 맵의 각 좌표에 전사 몇명씩 위치하는지 표시하기
for ax, ay in attackers:
if avail_maps[ax][ay] >= 0: # 메두사가 볼 수 있는 영역(0)에만
avail_maps[ax][ay] += 1 # 한 명당 + 1
# 돌이 된 전사 수 카운트
stone_cnt = 0
# 돌이 된 전사 좌표 리스트 -> 이후 전사 이동에서 제외해야 하므로
stones = []
# 메두사가 볼 수 있는 영역
medusa_sight = set()
# 메두사가 전사에 의해 가려져 보지 못하는 좌표 저장
cant_look_sight = set()
# 디버깅을 위해 메두사는 맵에 -2로 표기
avail_maps[sr][sc] = -2
while q:
x, y = q.popleft()
for k in range(4):
mx, my = x + dx[k], y + dy[k]
# 메두사가 볼 수 있는 영역, 아직 방문하지 않은 영역인 경우
if 0 <= mx < N and 0 <= my < N and avail_maps[mx][my] >= 0 and not visited[mx][my]:
# 전사를 찾은 경우 (1 이상이면 전사 있는 것)
if avail_maps[mx][my] >= 1:
# 해당 자리에 있는 돌이 될 전사 수 누적
stone_cnt += avail_maps[mx][my]
# 좌표도 누적
stones.append((mx, my))
# 전사의 뒤는 볼 수 없도록 맵에 0으로 처리하기
# 상
if d == 0:
# 메두사 위인 경우
if my == sc:
for i in range(1, mx + 1):
nx = mx - i
avail_maps[nx][my] = 0
# 메두사가 보지 못하는 영역을 따로 누적
cant_look_sight.add((nx, my))
# 메두사 기준 오른쪽인 경우
elif my > sc:
for i in range(1, mx + 1):
nx = mx - i
avail_maps[nx][my] = 0
cant_look_sight.add((nx, my))
# 메두사 기준 오른쪽
for j in range(1, i + 1):
ny = my + j
if 0 <= ny < N:
avail_maps[nx][ny] = 0
cant_look_sight.add((nx, ny))
# 메두사 기준 왼쪽인 경우
elif my < sc:
for i in range(1, mx + 1):
nx = mx - i
avail_maps[nx][my] = 0
cant_look_sight.add((nx, my))
# 메두사 기준 오른쪽
for j in range(1, i + 1):
ny = my - j
if 0 <= ny < N:
avail_maps[nx][ny] = 0
cant_look_sight.add((nx, ny))
# 하
elif d == 1:
# 메두사 아래인 경우
if my == sc:
for i in range(1, N - mx):
nx = mx + i
avail_maps[nx][my] = 0
cant_look_sight.add((nx, my))
# 메두사 기준 오른쪽인 경우
elif my > sc:
for i in range(1, N - mx):
nx = mx + i
avail_maps[nx][my] = 0
cant_look_sight.add((nx, my))
# 메두사 기준 오른쪽
for j in range(1, i + 1):
ny = my + j
if 0 <= ny < N:
avail_maps[nx][ny] = 0
cant_look_sight.add((nx, ny))
# 메두사 기준 왼쪽인 경우
elif my < sc:
for i in range(1, N - mx):
nx = mx + i
avail_maps[nx][my] = 0
cant_look_sight.add((nx, my))
# 메두사 기준 오른쪽
for j in range(1, i + 1):
ny = my - j
if 0 <= ny < N:
avail_maps[nx][ny] = 0
cant_look_sight.add((nx, ny))
# 좌
elif d == 2:
# 메두사 라인인 경우
if mx == sr:
for i in range(1, my + 1):
ny = my - i
avail_maps[mx][ny] = 0
cant_look_sight.add((mx, ny))
# 메두사 기준 위
elif mx < sr:
for i in range(1, my + 1):
ny = my - i
avail_maps[mx][ny] = 0
cant_look_sight.add((mx, ny))
# 메두사 기준 위
for j in range(1, i + 1):
nx = mx - j
if 0 <= nx < N:
avail_maps[nx][ny] = 0
cant_look_sight.add((nx, ny))
# 메두사 기준 아래
elif mx > sr:
for i in range(1, my + 1):
ny = my - i
avail_maps[mx][ny] = 0
cant_look_sight.add((mx, ny))
# 메두사 기준 아래
for j in range(1, i + 1):
nx = mx + j
if 0 <= nx < N:
avail_maps[nx][ny] = 0
cant_look_sight.add((nx, ny))
# 우
elif d == 3:
# 메두사 라인인 경우
if mx == sr:
for i in range(1, N - my):
ny = my + i
avail_maps[mx][ny] = 0
cant_look_sight.add((mx, ny))
# 메두사 기준 위
elif mx < sr:
for i in range(1, N - my):
ny = my + i
avail_maps[mx][ny] = 0
cant_look_sight.add((mx, ny))
# 메두사 기준 위
for j in range(1, i + 1):
nx = mx - j
if 0 <= nx < N:
avail_maps[nx][ny] = 0
cant_look_sight.add((nx, ny))
# 메두사 기준 아래
elif mx > sr:
for i in range(1, N - my):
ny = my + i
avail_maps[mx][ny] = 0
cant_look_sight.add((mx, ny))
# 메두사 기준 아래
for j in range(1, i + 1):
nx = mx + j
if 0 <= nx < N:
avail_maps[nx][ny] = 0
cant_look_sight.add((nx, ny))
visited[mx][my] = True
# 방문한 좌표는 메두사가 볼 수 있는 영역에 추가
medusa_sight.add((mx, my))
q.append((mx, my))
# 전사에 가려져 볼 수 없는 좌표를 제외해서 진짜 메두사가 볼 수 있는 좌표만 리턴하기
medusa_sight -= cant_look_sight
return stone_cnt, stones, medusa_sight
while True:
# 메두사의 집부터 공원까지 이어지는 도로가 없다면 -1 출력
if len(shortest_path) == 1:
print(-1)
break
# 1) 메두사의 이동
medusa_idx += 1
sr, sc = shortest_path[medusa_idx]
# 메두사가 이동한 칸에 전사가 있을 경우 바로 사라짐 주의!
while (sr, sc) in attackers:
attackers.remove((sr, sc))
# 메두사가 공원에 도착 시 종료
if sr == er and sc == ec:
print(0)
break
# 2) 메두사의 시선 -> 상 하 좌 우 순으로 볼 수 있는 전사 수 카운트
max_cnt = -1
medusa_d = -1
stone_list = set()
medusa_s = set()
# 전사를 가장 많이 볼 수 있는 방향을 바라보기
for i in range(4): # 0:상, 1:하, 2:좌, 3:우 우선순위
c, stones, medusa_sight = count_attacker(i)
if c > max_cnt:
max_cnt = c
medusa_d = i
sto = list(stones)
stone_list = set(sto)
medusa_s = set(medusa_sight)
# 3) 전사들의 이동 (돌 전사 제외하고)
# 첫 번째 이동
total_move = 0
for idx, (ax, ay) in enumerate(attackers):
# 돌이 되지 않았다면
if (ax, ay) not in stone_list:
# 이미 메두사 칸에 도달 시
if ax == sr and ay == sc:
continue
origin_dist = abs(ax - sr) + abs(ay - sc)
min_dist = float('inf')
next_x, next_y = -1, -1
# 상하좌우 순으로 확인
for i in range(4):
nx, ny = ax + dx[i], ay + dy[i]
# 메두사 시야에 포함되지 않는 칸으로 이동 가능
if 0 <= nx < N and 0 <= ny < N and (nx, ny) not in medusa_s:
# 맨해튼 거리 공식으로 해야 함 주의!
dist = abs(nx - sr) + abs(ny - sc)
# 기존 메두사와의 거리보다 더 줄어드는 경우에만 움직이기 주의!
if dist < min_dist and dist < origin_dist:
min_dist = dist
next_x = nx
next_y = ny
# 자리 갱신되었다면 반영
if next_x != -1 and next_y != -1:
attackers[idx] = (next_x, next_y)
total_move += 1
# 두 번째 이동
for idx, (ax, ay) in enumerate(attackers):
# 돌이 되지 않았다면
if (ax, ay) not in stone_list:
# 이미 메두사 칸에 도달 시 패스
if ax == sr and ay == sc:
continue
origin_dist = abs(ax - sr) + abs(ay - sc)
min_dist = float('inf')
next_x, next_y = -1, -1
dx2 = [0, 0, -1, 1]
dy2 = [-1, 1, 0, 0]
# 좌우상하 순으로 확인
for i in range(4):
nx, ny = ax + dx2[i], ay + dy2[i]
# 메두사 시야에 포함되지 않는 칸으로 이동 가능
if 0 <= nx < N and 0 <= ny < N and (nx, ny) not in medusa_s:
# 맨해튼 거리 공식으로 해야 함 주의!
dist = abs(nx - sr) + abs(ny - sc)
# 기존 메두사와의 거리보다 더 줄어드는 경우에만 움직이기 주의!
if dist < min_dist and dist < origin_dist:
min_dist = dist
next_x = nx
next_y = ny
# 자리 갱신되었다면 반영
if next_x != -1 and next_y != -1:
attackers[idx] = (next_x, next_y)
total_move += 1
attacked_cnt = 0
# 4) 전사의 공격
for ax, ay in attackers:
if ax == sr and ay == sc and (ax, ay) not in stone_list:
attacked_cnt += 1
# 죽은 전사 제외한 새로운 리스트 생성
new_attackers = [x for x in attackers if x != (sr, sc)]
attackers = new_attackers[:]
print(total_move, max_cnt, attacked_cnt)
