백준 2178번 : 미로 탐색 c++

코드

#include <iostream>
#include <string.h>
#include <queue>
#define MAX 101

using namespace std;

int N, M;
char map[MAX][MAX];
bool visited[MAX][MAX];
int dist[MAX][MAX];

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

queue<pair<int, int> > q;

void bfs(int x, int y){

	visited[x][y] = true;
	q.push(make_pair(x,y));
	dist[x][y]++;
	
	while(!q.empty()){
		int a = q.front().first;
		int b = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++){
			int next_x = a+dx[i];
			int next_y = b+dy[i];
			if(0<=next_x && next_x <N && 0<=next_y && next_y <M){
				if(!visited[next_x][next_y] && map[next_x][next_y] == '1'){
					q.push(make_pair(next_x, next_y));
					dist[next_x][next_y] = dist[a][b] + 1;
					visited[next_x][next_y] = true;
				}
			}
		}
	}	
}

int main(){
	
	cin >> N >> M;
	
	for(int i = 0; i < N; i++){
		memset(visited[i], false, sizeof(visited[i]));
	}
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cin >> map[i][j];
		}
	}
	
	bfs(0, 0);
	cout << dist[N-1][M-1];
	
	
	return 0;
}

알게된 점

미로찾기를 할 때에는 dfs의 시간이 매우 오래걸리기때문에 bfs를 이용해야한다.

그리고 dist라는 배열을 이용해 dp의 bottom up 방식과 유사하게 개수를 세어야 합니다.