[백준/BOJ] 2178번 미로 탐색 (C++)

www.acmicpc.net/problem/2178

2178번: 미로 탐색

BFS 유형의 문제입니다.

주의해야 할 점은 배열의 입력으로 받는 수가 붙어서 받아야 한다는 점입니다. 따라서 cin을 사용하지 않고 scanf를 이용하여 수를 입력받았습니다. (%1d 이런식으로 하면 수가 붙어서 입력되어도 하나씩 입력 받습니다.) 풀이는 그림 문제와 비슷합니다.

 

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

int n, m;
int map[101][101];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

struct Info {
	int x, y, sum;
};

int BFS(int r, int c, int sum) {
	queue<Info> q;
	q.push({r, c, sum});
	map[r][c] = 0;
	
	while(!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int sum = q.front().sum;
		q.pop();
		
		if(x == n && y == m) return sum;
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx >= 0 && nx <= n && ny >= 0 && ny <= m && map[nx][ny] == 1) {
				q.push({nx, ny, sum + 1});
				map[nx][ny] = 0;
			}
		}
	}
}

int main(void) {
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);
	
	scanf("%d %d", &n, &m);
	for(int i = 1 ; i <= n; i++) {
		for(int j = 1 ; j <= m; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	
	cout << BFS(1, 1, 1);
}