[BOJ/백준] 16509 장군 파이썬

문제 링크 : https://www.acmicpc.net/problem/16509

16509번: 장군

이동 규칙이 특이한 BFS 문제이다.

문제에 왕에 대한 규칙이 있지만 무시해도된다.

 

 

현재 점에서 상하좌우로 한칸 간후 해당 칸에서 대각으로 두칸을 이동한것이 한번의 움직임이다.

파란점이 상이 움직일 수 있는 구역이다.

그리고 움직이는 도중에 다른 말을 만나면 안된다. 왕도 해당 된다.

그리고 움직임의 끝에 왕과 만나야한다. 다시말해 위의 그림에 파란점에 왕이 있어야 만나는 것이다.

 

위에 그림대로 이동 규칙을 만들어서 BFS를 돌리면 된다.

여러 방법이 있겠지만 나는 이동방향을 총 8개로 나누었다.

0~3은 상하좌우, 4~7은 대각이다.

0으로 갔을 때는 대각은 4와 7이 매칭되고,

1로 갔을 때는 대각은 5와 4가 매칭된다.

이런식으로 방향을 매칭시켜줬고

한칸씩 이동하면서 왕이 있는지 체크해줬다.

 

from sys import stdin
from collections import deque

input = stdin.readline
dx = [-1,0,1,0,-1,1,1,-1]
dy = [0,1,0,-1,1,1,-1,-1]

r1,c1 = map(int, input().split())
r2,c2 = map(int, input().split())

def solv():
    visited = [[False]*9 for _ in range(10)]
    visited[r1][c1] = True

    q = deque([(r1,c1,0)])

    while q:
        x,y,cnt = q.pop()
        if x == r2 and c2 == y:
            print(cnt)
            return

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx,ny) and (nx != r2 or ny != c2):
                dd = d + 4
                for _ in range(2):
                    nnx,nny = nx,ny
                    flag = True
                    for c in range(2):
                        nnx = nnx + dx[dd]
                        nny = nny + dy[dd]
                        if not point_validator(nnx,nny) or (c == 0 and nnx == r2 and nny == c2):
                            flag = False
                            break
                    if flag and not visited[nnx][nny]:
                        visited[nnx][nny] = True
                        q.appendleft((nnx,nny,cnt+1))
                    dd = (dd-1)%4+4
    print(-1)

def point_validator(x,y):
    if x < 0 or y < 0 or x >= 10 or y >= 9:
        return False
    return True
solv()