백준 2178번 - 미로탐색

출처 : 2178번: 미로 탐색 (acmicpc.net)

2178번: 미로 탐색

---

미로 탐색 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초

192 MB

84405

32834

20926

37.654%

문제

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

---

[ 문제 설명 ]

 

이 문제는 주요한 점은 1,1에서 무조건 시작하여 좌표의 지도의 최대 크기 좌표가 도착점이라는 것이다. 그러므로 이에 맞게 코딩을 해주어야 한다.

일단 이문제는 1인 부분을 세는 점에서 토마토 문제와 상당히 유사하다.

 

그림으로 설명하겠다.

 

그림 1 - 미로 탐색 설명

BFS의 동작 방식을 상기하고 설명을 보면 이해가 가실 것.

---

[ 코드 ]

 

t, r = map(int, stdin.readline().split())
# matrix 배열
mazeSqure = [stdin.readline().rstrip() for _ in range(t)]
# 방문경로 배열
visited = [[0] * r for _ in range(t)]

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

# BFS 경로 탐색
# queue 방식 사용
queue = deque()
queue.append([0, 0])
visited[0][0] = 1

while queue:
    x, y = queue.popleft()

    if x == t - 1 and y == r - 1:
        # 최종 경로 도착
        print(visited[x][y])
        break

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < t and 0 <= ny < r:
            if visited[nx][ny] == 0 and mazeSqure[nx][ny] == '1':
                visited[nx][ny] = visited[x][y] + 1
                queue.append((nx,

BFS의 동작 방식을 안상태로 설명을 보시고, 코드를 보시면 이해가 될 것.

 

---

후기

 

왜 최솟값으로 출력해야 되는데, 최솟값을 표시하는 부분이 없을까?라는 생각이 든다면 BFS의 동작 방식을 한번 더 상기시켜 보시길