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

www.acmicpc.net/problem/2178

2178번: 미로 탐색

코드 설명

 bfs를 이용하여 map[][] 이 1일 때만 탐색하면서 기존 좌표에 +1을 해준다( ++을 하면 전부 증가하므로 오류)

 

도착 좌표에 도착하면 출력

 

입력이 빈칸이없기 때문에 string으로 받은 후 한 칸씩 int 형 변환하여 넣어주었다.

코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int map[101][101];
int N, M;

bool visited[101][101];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
void bfs(int y, int x) {
	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = true;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;

			if (!visited[ny][nx] && map[ny][nx] == 1) {
				map[ny][nx] = map[y][x]+1;
				q.push({ ny,nx });
				visited[ny][nx] = true;
			}
		}

	}

}
int main() {
	cin >> N >> M;


	for (int y = 0; y < N; y++)
	{
		string abc;
		cin >> abc;
		for (int i = 0; i < abc.size(); i++) {
			map[y][i] = abc[i] - '0';
		}
	}
	bfs(0, 0);
	cout << map[N - 1][M - 1];


	return 0;
}