뚝딱뚝딱

https://www.acmicpc.net/problem/2178

💡 미로 탐색

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

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

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

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

✅ 문제 풀이

• 처음에 시간초과가 발생했던 접근법

1. miro라는 함수를 호출하여 (0,0)부터 출발하고, 동,서,남,북에 있는 값이 1이면 각각의 위치에서 miro함수를 재귀호출하는 방식을 통해 count해 나간다.
2. 만약 miro함수에서 현재 위치가 (n-1,m-1)이면 현재까지의 count값과 answer값을 비교해서 작은 것을 answer로 갱신한다.

-> 이렇게 되면 n이 커질수록, 재귀호출 양이 많아져 시간 초과가 발생한다.

• queue를 이용해 재귀호출을 하지않고 count하는 방식으로 문제를 해결!

1. miro함수에 queue를 하나 생성한다. 
   이 queue는 pair로 <<행,렬>, count>로 데이터를 갖고 있다.
2. queue에 {{0,0},1}을 추가해서 (0,0)위치에서 1카운트 된 것을 queue에 집어넣는다.
3. 다음의 과정은 queue가 빌때까지 실행한다.
4. queue의 front에서 행의 값을 r에, 열의 값을 c에, count를 count에 넣는다.
5. 이제 여기는 방문한 것이므로 arr값을 0으로 바꾸어준다.
6. 현재 위치가 (n-1,m-1)인지 확인해서 맞다면, 현재의 count값과 기존의 최소 count가 저장된 answer를 비교해서 더 작은 값으로 갱신해준다.
7. 그리고 for문을 통해 현재 위치에서 상,하,좌,우에 있는 값이 1이면 queue에 해당 좌표와 현재의 count에서 +1한 값을 카운트로 넣어주고, 방문했음을 표시하기 위해 해당 위치의 arr값도 0으로 갱신해준다.
8. miro함수가 끝나고 나면 answer에는 최소 이동 값만이 저장된다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>

using namespace std;

int n, m;

int answer = 10000;

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

void miro(vector<vector<int>> &arr) {
	queue<pair<pair<int, int>, int>> q;
	q.push({ { 0, 0 }, 1 });
	arr[0][0] = 0;

	while (!q.empty()) {
		int r = q.front().first.first;
		int c = q.front().first.second;
		int count = q.front().second;

		q.pop();

		if (r == n - 1 && c == m - 1) {
			answer = min(answer, count);
			return;
		}

		for (int i = 0; i < 4; i++) {
			int x = r + dx[i];
			int y = c + dy[i];
			if (x >= 0 && x < n&&y >= 0 && y < m&&arr[x][y] == 1) {
				q.push({ {x,y}, count + 1 });
				arr[x][y] = 0;
			}
		}

	}

}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	vector<vector<int>> arr(n);

	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < str.length(); j++) {
			arr[i].push_back(str[j] - '0');
		}
	}

	miro(arr);

	cout << answer;
}