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

문제의 저작권은 SW Expert Academy에 있습니다.

def dfs(y, x):
    global res
    data[y][x] = 1
    for d in range(4):
        xf = dx[d] + x
        yf = dy[d] + y
        if (0<= xf < N) and (0 <= yf < N):
            if data[yf][xf] == 0:
              dfs(yf, xf)
            if data[yf][xf] == 3:
                res = 1
                return
 
 
TC= int(input())
for tc in range(1, TC+1):
    N = int(input())
    data = [list(map(int, input())) for _ in range(N)]
 
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
 
    for i in range(N):
        for j in range(N):
            if data[i][j] == 2:
                x = j
                y = i
 
    res = 0
    dfs(y, x)
 
    print("#%d %d"%(tc, res))

미로 문제같은 경우는 델타 탐색을 이용한다. 델타 탐색은 위의 dx, dy를 정의한 것이다.

 

하나 팁을 주자면 들어가자마자 반드시 visited부터 한다고 생각하자.