[SWEA] 4875_미로 (DFS 이용)

📕 문제

NxN 크기의 미로에서 출발지에서 목적지에 도착하는 경로가 존재하는지 확인하는 프로그램을 작성하시오. 도착할 수 있으면 1, 아니면 0을 출력한다.

주어진 미로 밖으로는 나갈 수 없다.

다음은 5x5 미로의 예이다.
 

13101

10101

10101

10101

10021

 

마지막 줄의 2에서 출발해서 0인 통로를 따라 이동하면 맨 윗줄의 3에 도착할 수 있는지 확인하면 된다. 

 

[입력]

첫 줄에 테스트 케이스 개수 T가 주어진다.  1<=T<=50

다음 줄부터 테스트 케이스의 별로 미로의 크기 N과 N개의 줄에 걸쳐 미로의 통로와 벽에 대한 정보가 주어진다. 0은 통로, 1은 벽, 2는 출발, 3은 도착이다. 5<=N<=100

 

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 계산결과를 정수로 출력하거나 또는 ‘error’를 출력한다.

 

💡 풀이법

1. 먼저 출발지(2)의 위치를아서 그 좌표에서부터 시작.

2. 현재 위치에서 갈수 있는 사방의 위치를 nx, ny로 만들고 0이면(갈 수 있는 통로이면) stack에 추가.

3. 만약 matrix[nx][ny]가 3이면 도착지에 도착한것이기 때문에 return 1.

4. stack을 다 돌아도 도착지에 도착을 못했다면 return 0.

 

def dfs(sy, sx):
    stack = [(sy, sx)]

    dyx = ((0, 1), (-1, 0), (1, 0), (0, -1)) # 갈 수 있는 방향
    while stack:
        y, x = stack.pop()
        maze[y][x] = 1

        for dy, dx in dyx:
            ny, nx = y + dy, x + dx

            if 0 <= ny <= N-1 and 0 <= nx <= N-1:
                if maze[ny][nx] == 0:
                    stack.append((ny, nx))
                elif maze[ny][nx] == 3:
                    return 1
    return 0

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    maze = [list(map(int, str(input()))) for _ in range(N)]
    for i in range(N):
        if 2 in maze[i]:
            sy, sx = i, maze[i].index(2)
            break
    print('#{} {}'.format(tc, dfs(sy, sx)))