[SWEA] 4875 - 미로

문제

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’를 출력한다.

풀이

잘 해결되지 않아 찾아보았는데
해를 찾는 도중 해가 아니어서 막히면 되돌아가서 해를 찾는 기법인 백트래킹 기법을 사용하였다. 0을 찾아서 가던중에 더이상 진행할 곳이 없는데 3(도착지점)이 아니면 스택에 저장되있지만 들르지 않은 곳으로 현재위치를 변경한다.
그 후에 다시 현재위치에서 상하좌우 중 갈곳을 찾고 다 했는데도 3(도착지점)을 갈 수 없으면 result=0이 출력되게 한다. 하지만 3(도착지점)을 찾으면 result=1이 출력된다.

코드

#상하좌우 확인
move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
T = int(input())
for test_case in range(1,T+1):
    N = int(input())
    maze = [list(map(int,input())) for _ in range(N)]
    start_x=start_y=0 #시작좌표
    result = 0 #결과
    #출발(2) 찾기
    for i in range(N):
        for j in range(N):
            if maze[i][j] == 2:
                start_x,start_y=j,i
    
    stack = [(start_y, start_x)] #내가 갈 수 있는 곳 저장하기위한 list

    while stack:
        y, x = stack.pop()
        maze[y][x] = 1 #현재 위치 방문처리
        #4방향 검사
        for _y, _x in move:
            dy = y + _y
            dx = x + _x
            if dy < 0 or dy >= N or dx < 0 or dx >= N: #범위 벗어나면
                continue # 상하좌우 중 다른곳 확인

            if maze[dy][dx] == 3: #도착
                result = 1
                break
            elif maze[dy][dx] == 0: #0이면 갈 수 있는 곳이니까 stack에 저장.
                stack.append((dy,dx))
        else: #for문이 브레이크 없이 끝나면(3을 못 만나면) while문 다시돌리기
            continue
        break
    print(f'#{test_case} {result}')