https://www.acmicpc.net/problem/16509
일반적이지만 살짝 귀찮은 bfs 문제다
저렇게 뛰는 친구들은 knight prob 비슷한 결로 아주 많이 나오고
거기에 visited 할 때마다 이전 노드 방문값 ++ 해주는 방법도 아주 쉽다
import sys
from collections import deque
input = sys.stdin.readline
n1, m1 = map(int, input().split())
# 상 우 하 좌
dir = [[-2, -3], [2, -3], [3, -2], [3, 2], [2, 3], [-2, 3], [-3, 2], [-3, -2]]
nodir = [
[[0, -1], [-1, -1]],
[[0, -1], [1, -1]],
[[1, 0], [2, -1]],
[[1, 0], [2, 1]],
[[0, 1], [1, 1]],
[[0, 1], [-1, 1]],
[[-1, 0], [-2, 1]],
[[-1, 0], [-2, -1]],
]
nox, noy = [], []
g = [[0] * 9 for _ in range(10)]
n2, m2 = map(int, input().split())
g[n2][m2] = 1
g[n1][m1] = 5
v = [[0] * 9 for _ in range(10)]
def bfs(x, y):
q = deque()
q.append((x, y))
v[y][x] = 1
while q:
cx, cy = q.popleft()
for idx, [dx, dy] in enumerate(dir):
f = False
nx, ny = cx + dx, cy + dy
for ex, ey in nodir[idx]:
nnx, nny = ex + cx, ey + cy
if 0 <= nnx < 9 and 0 <= nny < 10:
if g[nny][nnx] == 1:
f = True
break
# 중간에 뭐가 있으면 못감
if f:
continue
if 0 <= nx < 9 and 0 <= ny < 10 and v[ny][nx] == 0 and g[ny][nx] != 5:
q.append((nx, ny))
v[ny][nx] = v[cy][cx] + 1
if g[ny][nx] == 1:
return v[ny][nx]
res = bfs(m1, n1)
if res == 0:
print(-1)
else:
print(res - 1)bfs랑 그래프는 굉장히 익숙하다고 생각했는데 오래 걸렸다
지문을 잘못 읽어서 막고 있으면 못 간다는 게 왕이 막고 있어도 못 간다는 뜻인줄 몰랐음
그리고 중간 경로에 왕이 있는지 확인해야 하는데, 그 인덱스 하나하나 보고 입력하는 게 눈이 아픈 문제였다
