🦊 장군

1. 문제 링크

16509번: 장군

2. 코드

delta = [
    #위
    [(0, -1), (-1, -1), (-1, -1)],
    [(0, -1), (1, -1), (1, -1)],
    #오른쪽
    [(1, 0), (1, -1), (1, -1)],
    [(1, 0), (1, 1), (1, 1)],
    #아래
    [(0, 1), (1, 1), (1, 1)],
    [(0, 1), (-1, 1), (-1, 1)],
    #왼쪽
    [(-1, 0), (-1, -1), (-1, -1)],
    [(-1, 0), (-1, 1), (-1, 1)]
]

# 상
y1, x1 = map(int, input().split())
# 왕
y2, x2 = map(int, input().split())

# bfs
queue = [(x1, y1, 0)]
visit = []
for _ in range(10):
    visit.append([0] * 9)
visit[y1][x1] = 1

while queue:
    x, y, cnt = queue.pop(0)
    # print((x, y, cnt))
    # 왕 잡을수 있나 체크
    for arr in delta:
        tx = x
        ty = y
        for dx, dy in arr:
            tx += dx
            ty += dy
            
        if tx == x2 and ty == y2:
            print(cnt + 1)
            exit(0)

    for arr in delta:
        flag = 1
        tx = x
        ty = y
        for dx, dy in arr:
            tx += dx
            ty += dy
            # 중간 경로에 왕이 있으면 이동 불가
            if 0 <= tx <= 8 and 0 <= ty <= 9 and (tx, ty) != (x2, y2):
                flag = 1
            else:
                flag = 0
                break
        # 성공적으로 모두 이동했고 방문한적 없으면
        if flag == 1 and not visit[ty][tx]:
            # 왕 못잡으면 다시 시도
            visit[ty][tx] = 1
            # print(tx, ty)
            queue.append((tx, ty, cnt + 1))
print(-1)

Python3 31120kb 40ms

3. 해설

• 해설

  BFS 로 최단 경로 찾음

  단 움직이는 경로를 3단계로 나누어 더해주면서

  중간에 왕이 겹치는 경로가 있으면 움직이지 못하게 함