문제

• SWEA-4875 : [파이썬 S/W 문제해결 기본] 5일차 - 미로

풀이

bfs 방법을 사용하면 쉽게 해결된다.

def isSafe(ddx, ddy):
    return -1 < ddx < mazesize and -1 < ddy < mazesize and maze[ddx][ddy] != '1'


def bfs(maze):
    for i in range(mazesize):
        for j in range(mazesize):
            if maze[i][j] == '2':
                xs, ys = [i, j]

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

    visit = [[0]*mazesize for _ in range(mazesize)]
    queue = [[xs, ys]]
    visit[xs][ys] = 1
    while queue:
        x, y = queue.pop(0)
        for i in range(4):
            ddx = x + dx[i]
            ddy = y + dy[i]
            if isSafe(ddx, ddy) and visit[ddx][ddy] == 0:
                queue.append([ddx, ddy])
                visit[ddx][ddy] = 1
                if maze[ddx][ddy] == '3':
                    return 1
    return 0


T = int(input())
for test_case in range(1, T + 1):
    global mazesize
    mazesize = int(input())
    maze = []
    for i in range(mazesize):
        maze.append(''.join(input().split()))

    print('#%d %s' % (test_case, bfs(maze)))