[SW Expert Academy] 4875. 미로

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

 

 

풀이)

def dfs():
    while stack:
        a, b = stack.pop()
        li[a][b] = "1"
        for i in range(4):
            o = a + di[i]
            x = b + dj[i]
            if -1 < o < n and -1 < x < n: # 해당 범위 안에서 활동
                if li[o][x] == "0": # 이동할 수 있으면 스택에 넣는다.
                    stack.append([o, x])
                elif li[o][x] == "3":
                    return 1
    return 0
 
T = int(input())
for _ in range(T):
    n = int(input())
    li = [list(input()) for i in range(n)]
    stack = [] # 미로의 경우의 수를 다 찾아야 하므로 스택을 이용한다.
    
    for i in range(n): # a, b는 2의 인덱스. // 시작점 찾기
        for j in range(n):
            if li[i][j] == "2":
                a = i
                b = j
                stack.append([a, b])
    
    di = [1, -1, 0, 0] # 상 하 좌 우 // 델타 이동
    dj = [0, 0, -1, 1]
 
    print(f"#{_ + 1} {dfs()}")

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.