(BOJ) 2178번 풀이

#include<iostream>
#include<queue>
#include<string>

using namespace std;
queue<pair<int,int>>q;
int N,M,map[102][102]={0,},chk[101][101];
void BFS(int x,int y, int c){
	q.push(pair<int,int>(y,x));
	chk[y][x]=c;
	while(!q.empty()){
		int cx = q.front().first;
        int cy = q.front().second;
		q.pop();
		// cout << '(' << cx << ',' << cy << ") : " << chk[cx][cy] << endl;
		if(cx==N&&cy==M){
			cout << chk[N][M] << endl;
			break;
		}
		if(map[cx-1][cy]){
			if(!chk[cx-1][cy]){
			q.push(pair<int,int>(cx-1,cy));
			chk[cx-1][cy]=chk[cx][cy]+1;
			}
		}
		if(map[cx+1][cy]){
			if(!chk[cx+1][cy]){
			q.push(pair<int,int>(cx+1,cy));
			chk[cx+1][cy]=chk[cx][cy]+1;
			}
		}
		if(map[cx][cy+1]){
			if(!chk[cx][cy+1]){
			q.push(pair<int,int>(cx,cy+1));
			chk[cx][cy+1]=chk[cx][cy]+1;
			}
		}
		if(map[cx][cy-1]){
			if(!chk[cx][cy-1]){
			q.push(pair<int,int>(cx,cy-1));
			chk[cx][cy-1]=chk[cx][cy]+1;
			}
		}
	}
}
int main(void){
	cin >> N >> M;
	string s;
	for(int i=0;i<N;i++){
		cin >> s;
		for(int j=0;j<s.size();j++){
			map[i+1][j+1]=s[j]-'0';
		}
		s="";
	}
	BFS(1,1,1);
}

배열을 102 으로 선언해서 0으로 초기화 한다.

그래야 cx, cy 에 +1 해도 oob 가 안나 map 을 벗어나도 0이기 때문에 map 에 있는지 아닌지 검사할 수 있다.

방문한곳은 chk 로 얼마나 움직였는지 표시하면서 큐랑 pair 로 BFS 하면 된 다.