[백준문제풀이] 2178 미로 탐색

 

풀이 일시 : 2020-10-13

​

 

문제 :

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

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

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

​

​

입력 :

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

ex)

4 6

101111

101010

101011

111011

​

​

출력 :

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

ex)

15

​

​

풀이 :

상하좌우를 탐색하며 1인 길로만 갈 수 있다. 최단경로 이므로 bfs를 먼저 생각해보자.

큐에 담으며 진행하며 최단거리를 찾을 수 있다.

​

이 문제를 풀며 애먹었던 부분은 바로 이 부분이다.

회색부분이 지금까지 지나쳐 온 경로이고 초록색이 현재 4방향 탐색을 실행하고 있는 노드이다. 초록색에서 만약 오른쪽 빨간색 노드를 먼저 탐색한다면 count +1 될 것이고 노란색 부분으로 다시 경로를 잡는다고 해도 옳지 않은 경로에 ++를 해준 격이 될 것이다. 즉 빨간색을 거쳤다 노란색을 가면 초록색에서 노란색을 바로 가는것에 비해 count가 + 1 될것이라는 말.

 

그래서 빨간색과 노란색을 같이 count++ 시켜 줘야 할 것이다. 방법은

queue<pair <pair <int좌표1,int좌표2>, int카운트>> q; //이다.

 

cnt = q.front().second로 잡아두고 하나의 queue에 대한 작업을 시작한다면 4방향 탐색시 삽입되는 것들에 cnt+1만 해주어 계속되어 ++되지 않아도 될 것이다.

사용 : q.push({ex,ey},cnt+1});

 

#include <iostream>
#include <queue>
#include <vector>
#define MAX 101
using namespace std;

int graph[MAX][MAX] = { 0, };
int visit[MAX][MAX] = { 0, };
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 }; //하 우 상 좌 순서로 탐색하게 함 상관은없음
int Y, X, s;

int bfs(int x, int y, int cnt) {
	queue <pair <pair <int, int>, int>> q;
	q.push({{ x, y }, cnt});
	visit[x][y] = true;

	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		cnt = q.front().second; //앞서 말했던 부분이다 4방향 탐색전 현재 cnt를 잡고가자
		q.pop();

		if (x == X-1 && y == Y-1) 
			return cnt;

		for (int i = 0; i < 4; i++) {
			int ex = x + dx[i];
			int ey = y + dy[i];
			if (ex < 0 || ex >= X || ey < 0 || ey >= Y)
				continue;

			if (!visit[ex][ey] && graph[ex][ey]) {
				visit[ex][ey] = true;
				q.push({{ ex,ey }, cnt + 1});//아까 설정해둔 cnt에 +1만 더하면 될것
			}
		}
	}
}


int main(){
	cin >> X >> Y;
	for (int i = 0; i < X; i++) {
		for (int j = 0; j < Y; j++) {
			scanf_s("%1d", &s); //글자를 하나씩 읽어온다.
			graph[i][j] = s;
		}
	}
	cout << bfs(0,0,1) << endl;

}

 

참고자료 : input방법들

dbstndi6316.tistory.com/33

[개념정리] C++ 여러 input방법에 대해