백준 알고리즘 9311번 Robot in a Maze(python)

간단한 BFS 문제이다.

S에서 G로 가는 최단경로의 길이를 출력해주면 된다. 경로가 없다면 No Exit 출력

from collections import deque

def bfs(i, j):
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    q = deque()
    q.append((i, j))
    check[i][j] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < R) and (0 <= X < C) and graph[Y][X] != 'X' and check[Y][X] == -1:
                check[Y][X] = check[y][x] + 1
                if graph[Y][X] == 'G':
                    return check[Y][X]
                q.append((Y, X))
    return None

for _ in range(int(input())):
    R, C = map(int, input().split())
    graph = [input() for a in range(R)]
    check = [[-1]*C for b in range(R)]
    
    for i in range(R):
        for j in range(C):
            if graph[i][j] == 'S':
                ans = bfs(i, j)
                print(f"Shortest Path: {ans}" if ans else "No Exit")