5일차 - 미로

def DFS(start):
    matrix[start[0]][start[1]] = 9

    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    for i in range(4):
        x = start[0] + dx[i]
        y = start[1] + dy[i]

        if 0 <= x < n and 0 <= y < n and (matrix[x][y] == 0 or matrix[x][y] == 3):
            DFS((x,y))

t = int(input())
ans = list()

for _ in range(t):
    n = int(input())
    matrix = [list(map(int, input().rstrip())) for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if matrix[i][j] == 2:
                start_point = (i, j)
            if matrix[i][j] == 3:
                object_point = (i, j)

    DFS(start_point)

    if matrix[object_point[0]][object_point[1]] == 9:
        ans.append(1)
    else:
        ans.append(0)

for i in range(t):
    print(f"#{i+1} {ans[i]}")

 

DFS 기본 문제이다!

최적화 할 방법이 더 있을 것 같은데 일단 여기서 마무리 했당..

 

DFS 돌려서 방문한 지점을 9로 바꿔주고 object_point에 해당하는 좌표값이 9면 True로, 9가 아닌 3이면 False로 나오도록 구현하였다