BOJ 9311 - Robot in a Maze

문제

백준 온라인 저지 - 9311번

풀이 과정

시작 지점에서 목표 지점에 도달하기 위한 최단 이동 횟수를 구하는 전형적인 BFS 문제입니다.

보드를 입력받은 다음 시작 지점을 먼저 찾은 다음, BFS 를 통해서 목표 지점 G 를 찾을 때까지 순회합니다.

코드

import sys
from collections import deque


dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def pre_processing(board, R, C):
    for x in range(R):
        for y in range(C):
            if board[x][y] == 'S':
                return [x, y]


def bfs(start, board, R, C):
    q = deque()
    visit = [[0] * C for _ in range(R)]

    q.append([*start, 0])
    visit[start[0]][start[1]] = 1

    while q:
        x, y, cost = q.popleft()

        if board[x][y] == 'G':
            return cost

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

            if 0 <= nx < R and 0 <= ny < C:
                if board[nx][ny] in ['O', '0', 'G'] and not visit[nx][ny]:
                    visit[nx][ny] = 1
                    q.append([nx, ny, cost + 1])

    return 0


def solution(board, R, C):
    start = pre_processing(board, R, C)
    cost = bfs(start, board, R, C)

    return cost


if __name__ == '__main__':
    T = int(input())

    for _ in range(T):
        R, C = list(map(int, sys.stdin.readline().split()))
        board = [list(sys.stdin.readline().strip()) for _ in range(R)]

        answer = solution(board, R, C)

        if answer:
            print(f"Shortest Path: {answer}")
        else:
            print("No Exit")