문제 출처 : [SWEA] 4875 미로
learn -> course -> programming intermediate -> stack2 -> 미로

문제

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

코드

# 목표지점을 찾는 함수(시작위치의 좌표)
def find_goal(start_x, start_y):
    dx = [1, -1, 0, 0]      # 시작위치로 부터 4방향 탐색 오른쪽, 왼쪽, 위, 아래
    dy = [0, 0, -1, 1]
    stack = [(start_x, start_y)]    # 스택에 현재 좌표 넣어주기
    # 스택이 빌 때까지 반복
    while stack:
        now_x, now_y = stack.pop()  # 스택에서 현재 좌표를 받아옴
        visited[now_y][now_x] = 1   # 현재 좌표 방문 표시

        # 미로의 현재 좌표 값이 3이면 return 1
        if maze[now_y][now_x] == 3:
            return 1

        # 델타 값을 변경하면서 주위에 이동할 수 있는 위치 탐색
        for i in range(4):
            next_x = now_x + dx[i]  # 현재 델타 값을 더한 좌표
            next_y = now_y + dy[i]
            # 좌표 값이 인덱스를 벗어나지 않고, 방문한 적 없는 위치이고, 미로의 벽이 아닐 경우
            if 0 <= next_x < N and 0 <= next_y < N and not visited[next_y][next_x] and maze[next_y][next_x] != 1:
                # 방문 여부를 1로 바꾸고 스택에 추가
                visited[next_y][next_x] = 1
                stack.append((next_x, next_y))
    return 0


T = int(input())
for tc in range(1, T + 1):
    N = int(input())
    maze = [list(map(int, input())) for _ in range(N)]  # 미로의 좌표
    visited = [[0] * N for _ in range(N)]   # 방문 여부를 저장할 2차원 리스트
    start_x = 0     # 시작 위치의 좌표를 저장할 변수 초기화
    start_y = 0
    flag = 0

    for i in range(N):
        for j in range(N):
            if maze[i][j] == 2:     # 시작 위치의 인덱스 값을 변수에 저장
                start_x = j
                start_y = i
                flag = 1
                break       # 시작 지점을 찾았으면 break
        if flag:
            break

    print(f'#{tc} {find_goal(start_x, start_y)}')

풀이 방법

bfs를 활용하여 문제를 풀었고 우선 시작 위치를 찾아서 함수의 인자로 넘겨주었다. 스택에 시작 좌표를 넣어주고 while문 안에서 pop해주면서 이동할 수 있는 위치들을 찾았다. while문 내부에서 도착지점을 찾았을 경우 바로 종료되도록 해주었다. 그리고 이동할 수 있는 방향이 4방향이므로 4방향을 탐색할 때 해당 위치가 인덱스를 벗어나지 않고 방문하지 않은 위치이고 벽이 아니면 해당 위치를 queue에 넣어주는 방식으로 풀이하였다.