[SWEA][Python] 1226 미로1

도착 가능한지 여부만 판단하면 됨. dfs

 

import sys
sys.stdin = open('input.txt')


def dfs(x,y):
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0 <= nx < 16 and 0 <= ny < 16 and not visited[nx][ny]:
            if not maze[nx][ny]:
                visited[nx][ny] = True
                if dfs(nx, ny):
                    return True
            elif maze[nx][ny] == 3:
                return True


def find_start(maze):
    for i in range(16):
        for j in range(16):
            if maze[i][j] == 2:
                return 1 if dfs(i, j) else 0


for _ in range(10):
    test = int(input())
    maze = [list(map(int, list(input()))) for _ in range(16)]
    visited = [[False for _ in range(16)] for _ in range(16)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    print(f'#{test} {int(find_start(maze))}')