[BOJ/백준] 2178번 미로탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

---

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

---

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

입/출력

---

풀이

n,m= map(int,input().split())

graph = []
for _ in range(n):
    graph.append(list(map(int,input())))
visited = [[0] * m for i in range(n)]

dx = [-1,0,1,0]
dy = [0,-1,0,1]

queue = [(0,0)]
visited [0][0] = 1
 
while queue:
    x,y = queue.pop(0)
    if x == n - 1 and y == m - 1:
        print(visited[x][y])
        break
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<n and 0<=ny<m:
            if visited[nx][ny] == 0 and graph[nx][ny] == 1:
                visited[nx][ny] = visited[x][y] + 1
                queue.append((nx,ny))

결과

---

문제 풀이

1. 미로를 입력받을 배열 graph 와 방문 처리를 할 visited를 0을 가진 2차원 배열로 선언
2. dx, dy라는 상하좌우 배열을 체크할 배열 선언
3. 조건에 맞는 배열을 넣을 queue를 선언
4. 최종 경로에 도착했다면 방문 배열을 출력
5. 아니라면 상하좌우를 탐색하면서 조건에 맞다면 방문 여부 수정 후 , 큐에 삽입