[BOJ] 16509. 장군(Python) / BFS

16509번: 장군

10×9 크기의 장기판 위에 상과 왕의 처음 위치가 주어졌을 때, 상이 왕에게 도달할 수 있는 최소 이동 횟수 구하기

단, 이동 중 기물 있다면 해당 방향으로 이동하지 못한다.

# 55분 소요

• 사용 알고리즘 : BFS 최단 거리 구하기
• 문제 그리기 전에 상이 갈 수 있는 8방향 델타 좌표(dr, dc), 위치별 장애물 좌표(obstacle)를 만들어뒀다.
• bfs에서 상의 첫 위치를 0으로 표현하고 큐에 담는다.
• 큐에서 꺼낸 위치에서 8방향 중 갈 수 있는 곳을  모두 board에 표시한다.
  • 이동 중 격자 밖으로 나가거나 이미 방문한 곳이면 continue
  • 이동 중 장애물(왕) 만나면 flag가 False로 바뀌며 해당 방향으로 이동 못하도록 continue
  • 이동 중 왕 만나면 해당 거리 리턴
  • 정상적으로 이동 가능하다면 현 위치 + 1한 값을 새 위치에 board에 표시하고 큐에 담기
  • 큐가 빌 때까지 왕이 있는 곳에 도달하지 못하면 -1을 리턴

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline
from collections import deque

# 상이 갈 수 있는 곳
dr = (-3, -2, 2, 3, 3, 2, -2, -3)
dc = (2, 3, 3, 2, -2, -3, -3, -2)

# 위치별 장애물
obstacle = {0: ((-1, 0), (-2, 1)),
            1: ((0, 1), (-1, 2)),
            2: ((0, 1), (1, 2)),
            3: ((1, 0), (2, 1)),
            4: ((1, 0), (2, -1)),
            5: ((0, -1), (1, -2)),
            6: ((0, -1), (-1, -2)),
            7: ((-1, 0), (-2, -1))}

def bfs():
    board = [[0] * 9 for _ in range(10)]
    board[sr][sc] = 1
    Q = deque([(sr, sc)])
    while Q:
        r, c = Q.popleft()            
        for d in range(8):
            nr = r + dr[d]
            nc = c + dc[d]
            # 격자 밖으로 나가거나 이미 방문했다면
            if not (0 <= nr < 10 and 0 <= nc < 9) or board[nr][nc]:
                continue

            # 이동 중 장애물(왕) 만나면
            flag = True
            for wr, wc in obstacle[d]:
                if (r+wr, c+wc) == (kr, kc):
                    flag = False    # 그 방향으로 이동 불가 표시
                    break
            if not flag:
                continue

            if (nr, nc) == (kr, kc):    # 왕 만나면 최단 거리 리턴
                return board[r][c]
                
            # 정상 이동
            board[nr][nc] = board[r][c] + 1
            Q.append((nr, nc))
    
    return -1   # 왕에 도달하지 못하면 -1 리턴

# main
sr, sc = map(int, input().split())  # 상 위치
kr, kc = map(int, input().split())  # 왕 위치
print(bfs())

---

• 시간 : 144ms / 메모리 : 123560kb
• 고찰 : 깔끔한 bfs 문제였다. 그런 것 치곤 중간에 장애물 처리 때문에 좀 헤매서 꽤 시간이 걸렸다ㅠㅠ 더 더 열심히 하자!