📚문제: #16509 장군(Gold 5)
오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 상을 어떻게 써야 할지 도와주자.
위 그림은 10×9 크기의 장기판을 나타내며, 상은 (5, 4)에, 왕은 (1, 4)에 자리 잡고 있는 기물이다. (0, 3)과 (2, 5)를 꼭짓점으로 하는 사각형과, (7, 3)과 (9, 5)를 꼭짓점으로 하는 사각형은 왕이 위치할 수 있는 궁성이라고 한다. 상은 위 그림과 같이 8가지 방법으로 움직일 수 있는데, 상, 하, 좌, 우로 한 칸을 이동한 후에 같은 방향 쪽 대각선으로 두 칸 이동한다.
만약 상이 이동하는 경로에 위 그림과 같이 다른 기물이 있다면 상은 그쪽으로 이동할 수 없다. 또한, 상이 장기판을 벗어날 수도 없다.
10×9 크기의 장기판 위에 상과 왕의 처음 위치가 주어졌을 때, 상이 왕에게 도달할 수 있는 최소 이동 횟수를 구하여라.
입력
첫 번째 줄에는 상의 위치를 의미하는 정수 R1, C1이 주어진다.
두 번째 줄에는 왕의 위치를 의미하는 정수 R2, C2가 주어진다. 장기판에서 Ri (0 ≤ Ri ≤ 9)는 행을, Ci (0 ≤ Ci ≤ 8)는 열을 의미한다.
왕은 항상 궁성에 자리 잡고 있으며, 상과 왕의 위치는 겹치지 않는다.
출력
상이 왕에게 도달할 수 있는 최소 이동 횟수를 출력한다. 만약 도달할 수 없다면 -1을 출력한다.
예제 입력 1
4 2
2 5예제 출력 1
1예제 입력 2
0 1
8 4예제 출력 2
3예제 입력 3
0 2
1 4예제 출력 3
5아이디어 및 구현
- 상의 이동가능 방향 8가지를 고려하여 알고리즘을 작성한다.
dr = [-3, -2, 2, 3, 3, 2, -2, -3]
dc = [2, 3, 3, 2, -2, -3, -3, -2]
- 상이 이동하는 경로에 왕이 있어 지나가지 못하는 상황을 반영하여 알고리즘을 작성한다.
cur_r, cur_c = queue.popleft()
# R2, C2는 왕의 위치
# 아래는 i == 0 일 때 코드, i = 1 ~ 7에 대해서도 작성
for i in range(8):
if i == 0:
# 상의 이동경로 1
if cur_r - 1 == R2 and cur_c == C2:
continue
# 상의 이동경로 2
elif cur_r - 2 == R2 and cur_c + 1 == C2:
continue
else:
move_r, move_c = cur_r + dr[i], cur_c + dc[i]
# 장기판을 벗어나지 않으면서 아직 방문하지 않은 지점일 때
if 0 <= move_r <= 9 and 0 <= move_c <= 8:
if area[move_r][move_c] == 0:
area[move_r][move_c] = area[cur_r][cur_c] + 1
queue.append([move_r, move_c])전체 코드
import sys
from collections import deque
# BFS Algorithm
def BFS(area, cur):
# 상이 움직일 수 있는 8방향
dr = [-3, -2, 2, 3, 3, 2, -2, -3]
dc = [2, 3, 3, 2, -2, -3, -3, -2]
queue = deque([cur])
cur_r, cur_c = cur
area[cur_r][cur_c] = 1
# Queue가 빌 때까지 반복
while queue:
cur_r, cur_c = queue.popleft()
for i in range(8):
if i == 0:
if cur_r - 1 == R2 and cur_c == C2:
continue
elif cur_r - 2 == R2 and cur_c + 1 == C2:
continue
else:
move_r, move_c = cur_r + dr[i], cur_c + dc[i]
# 장기판을 벗어나지 않으면서 아직 방문하지 않은 지점일 때
if 0 <= move_r <= 9 and 0 <= move_c <= 8:
if area[move_r][move_c] == 0:
area[move_r][move_c] = area[cur_r][cur_c] + 1
queue.append([move_r, move_c])
if i == 1:
if cur_r == R2 and cur_c + 1 == C2:
continue
elif cur_r - 1 == R2 and cur_c + 2 == C2:
continue
else:
move_r, move_c = cur_r + dr[i], cur_c + dc[i]
# 장기판을 벗어나지 않으면서 아직 방문하지 않은 지점일 때
if 0 <= move_r <= 9 and 0 <= move_c <= 8:
if area[move_r][move_c] == 0:
area[move_r][move_c] = area[cur_r][cur_c] + 1
queue.append([move_r, move_c])
if i == 2:
if cur_r == R2 and cur_c + 1 == C2:
continue
elif cur_r + 1 == R2 and cur_c + 2 == C2:
continue
else:
move_r, move_c = cur_r + dr[i], cur_c + dc[i]
# 장기판을 벗어나지 않으면서 아직 방문하지 않은 지점일 때
if 0 <= move_r <= 9 and 0 <= move_c <= 8:
if area[move_r][move_c] == 0:
area[move_r][move_c] = area[cur_r][cur_c] + 1
queue.append([move_r, move_c])
if i == 3:
if cur_r + 1 == R2 and cur_c == C2:
continue
elif cur_r + 2 == R2 and cur_c + 1 == C2:
continue
else:
move_r, move_c = cur_r + dr[i], cur_c + dc[i]
# 장기판을 벗어나지 않으면서 아직 방문하지 않은 지점일 때
if 0 <= move_r <= 9 and 0 <= move_c <= 8:
if area[move_r][move_c] == 0:
area[move_r][move_c] = area[cur_r][cur_c] + 1
queue.append([move_r, move_c])
if i == 4:
if cur_r + 1 == R2 and cur_c == C2:
continue
elif cur_r + 2 == R2 and cur_c - 1 == C2:
continue
else:
move_r, move_c = cur_r + dr[i], cur_c + dc[i]
# 장기판을 벗어나지 않으면서 아직 방문하지 않은 지점일 때
if 0 <= move_r <= 9 and 0 <= move_c <= 8:
if area[move_r][move_c] == 0:
area[move_r][move_c] = area[cur_r][cur_c] + 1
queue.append([move_r, move_c])
if i == 5:
if cur_r == R2 and cur_c - 1 == C2:
continue
elif cur_r + 1 == R2 and cur_c - 2 == C2:
continue
else:
move_r, move_c = cur_r + dr[i], cur_c + dc[i]
# 장기판을 벗어나지 않으면서 아직 방문하지 않은 지점일 때
if 0 <= move_r <= 9 and 0 <= move_c <= 8:
if area[move_r][move_c] == 0:
area[move_r][move_c] = area[cur_r][cur_c] + 1
queue.append([move_r, move_c])
if i == 6:
if cur_r == R2 and cur_c - 1 == C2:
continue
elif cur_r - 1 == R2 and cur_c - 2 == C2:
continue
else:
move_r, move_c = cur_r + dr[i], cur_c + dc[i]
# 장기판을 벗어나지 않으면서 아직 방문하지 않은 지점일 때
if 0 <= move_r <= 9 and 0 <= move_c <= 8:
if area[move_r][move_c] == 0:
area[move_r][move_c] = area[cur_r][cur_c] + 1
queue.append([move_r, move_c])
if i == 7:
if cur_r - 1 == R2 and cur_c == C2:
continue
elif cur_r - 2 == R2 and cur_c - 1 == C2:
continue
else:
move_r, move_c = cur_r + dr[i], cur_c + dc[i]
# 장기판을 벗어나지 않으면서 아직 방문하지 않은 지점일 때
if 0 <= move_r <= 9 and 0 <= move_c <= 8:
if area[move_r][move_c] == 0:
area[move_r][move_c] = area[cur_r][cur_c] + 1
queue.append([move_r, move_c])
# 상의 위치가 주어집니다.
R1, C1 = map(int, sys.stdin.readline().split())
# 왕의 위치가 주어집니다.
R2, C2 = map(int, sys.stdin.readline().split())
# 장기판을 초기화합니다. 10x9 크기
board = [[0] * 9 for _ in range(10)]
# BFS 알고리즘 실행
BFS(board, [R1, C1])
if board[R2][C2] == 0:
print(-1)
else:
print(board[R2][C2]-1)