[SW Expert Academy] 1226. 미로 1

1226. 미로 1

---

문제)

 

아래 그림과 같은 미로가 있다. 16*16 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다.

가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다.

주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라.

아래의 예시에서는 도달 가능하다.

 

 

아래의 예시에서는 출발점이 (1, 1)이고, 도착점이 (11, 11)이며 도달이 불가능하다.

 

 

 

[입력]

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트케이스가 주어진다.

테스트 케이스에서 1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다.

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도달 가능 여부를 1 또는 0으로 표시한다 (1 - 가능함, 0 - 가능하지 않음).

 

 

 

풀이)

 

from collections import deque
 
def BFS():
    
    # 4방향 탐색
    di = [-1, 1, 0, 0]
    dj = [0, 0, -1, 1]
 
    # BFS
    while queue:
        a, b = queue.popleft()
        for i in range(4):
            x = a + di[i]
            y = b + dj[i]
            # 미로 범위 내에서만 이동한다.
            if -1 < x < 16 and -1 < y < 16:
 
                # 목적지에 도달하면 1을 return
                if g[x][y] == "3":
                    return 1
 
                # 길을 찾아 헤메는중..
                if g[x][y] == "0":
                    g[x][y] = -1
                    queue.append([x, y])
    
    # 모든 길을 돌아도 목적지에 도달하지 못했으면,
    else:
        return 0
 
for _ in range(1, 11):
    # n번째 테스트 케이스
    n = int(input())
    # 미로 입력 받기
    g = [list(input()) for i in range(16)]
    queue = deque()
    # 출발 인덱스는 [1, 1]
    queue.append([1, 1])
    print(f'#{n} {BFS()}')

---

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

SW Expert Academy

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

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