미로탐색 #2178 c++ 문제풀이

 

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

2178번: 미로 탐색

bfs문제는 이제 유형을 보면 바로 알아챌 수 있다.

알게 된 점은 구현에서 

이제 큐나 다른 것을 건들이지 않고(bfs의 최초 형태를 살리는 방향으로), 다른 자료구조를 추가해서 탐색에 대한 기록을 해주는 것이 유리하다는 것을 깨달았다.

 

경로를 기록하면서 갈수있는 방향에 대한 ans값을 기록한다.

그리고, 도착지점의 ans값을 출력하면 된다.

 

 

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


int graph[101][101];
int visited[101][101];
int ans[101][101];

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


void bfs(int y, int x) {
	queue<pair<int, int>> q;
	q.push(make_pair(y, x));

	ans[y][x] = 1;
	

	while (!q.empty()) {

		int y = q.front().first;
		int x = q.front().second;
		visited[y][x] = 1;

		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (nx < 0 || nx >= M || ny < 0 || ny >= N)
				continue;
			if (graph[ny][nx] == 0)
				continue;
			if (graph[ny][nx] == 1 && visited[ny][nx] == 0)
			{
				ans[ny][nx] = ans[y][x] + 1;
				q.push(make_pair(ny, nx));
				visited[ny][nx] = 1;
			}
		}
	}
	

}
int main() {
	
	cin >> N >> M;
	string temp;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		for (int j = 0; j < M; j++) {
			if (temp[j] == '0')
				graph[i][j] = 0;
			else
				graph[i][j] = 1;
		}
	}
	//for (int i = 1; i <= N; i++) {
	//	for (int j = 1; j <= M; j++) {
	//		cout << graph[i][j] << " ";
	//	}
	//	cout << endl;
	//}
	bfs(0,0);
	//for (int i = 0; i < N; i++) {
	//	for (int j = 0; j < M; j++)
	//		cout << ans[i][j]<< " ";
	//	cout << '\n';
	//}
    cout << ans[N-1][M-1] << end;
	return 0;
}