BOJ 2178 미로 탐색

문제출처 : https://www.acmicpc.net/problem/2178

1. 문제요약

- n * m 크기의 맵이 주어짐

- 1은 갈 수 있는 곳, 0은 갈 수 없는 곳

- (1, 1) 에서 출발해서 (n, m) 까지 지나는 최소 칸수는?

- (1, 1), (n, m) 도 칸 횟수에 포함

- 2 <= n, m <= 100

2. 접근방법

- 맵 최소 이동횟수 = bfs

3. 시간복잡도

- O(n*m)

4. 회고

소스코드

#include<iostream>
#include<queue>
using namespace std;

int n, m, ans;
char map[101][101];
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, -1, 0, 1 };

int main(void){
	cin >> n >> m;
	for (int i = 0; i < n; i++){
		cin >> map[i];
	}

	queue<pair<pair<int, int>, int> *gt; q;
	q.push(make_pair(make_pair(0, 0), 1));
	map[0][0] = '0';

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

		if (r == n - 1 && c == m - 1){
			ans = cnt;
			break;
		}

		for (int k = 0; k < 4; k++){
			int nr = r + dr[k];
			int nc = c + dc[k];

			if (0 <= nr && nr < n && 0 <= nc && nc < m && map[nr][nc] == '1'){
				q.push(make_pair(make_pair(nr, nc), cnt + 1));
				map[nr][nc] = '0';
			}
		}
	}

	cout << ans << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]