[백준] 2178 미로탐색

백준 2178 미로탐색 바로가기

C++ 코드

#include<iostream>
#include<cstdio>
#include<queue>
#define MAXV 101
using namespace std;
int N, M;

char map[MAXV][MAXV] = { 0 };
int visit[MAXV][MAXV] = { 0 };
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; //(y,x) 위,아래,오른쪽,왼쪽


int isInside(int a, int b) {
	return (a >= 0 && a < N) && (b >= 0 && b < M);
}


int bfs() {
	int cur_y = 0, cur_x = 0;

	queue<pair<int, int>> q;
	q.push(pair<int, int>(cur_y, cur_x));
	visit[cur_y][cur_x] = 1;

	while (!q.empty()) {
		
		//큐의 가장 앞에 있는 노드를 pop
		cur_y = q.front().first;
		cur_x = q.front().second;
		q.pop();

		//현재 노드에 인접한 모든 노드들(상 하 좌 우)
		for (int i = 0; i < 4; i++) { //4방향 순회, up down left right
			int next_y = cur_y + dir[i][0];
			int next_x = cur_x + dir[i][1];

			//해당 점이 맵 내부에 있고, 방문한 적 없고, 길인지(1인지)
			if (isInside(next_y, next_x) && visit[next_y][next_x] == 0 && map[next_y][next_x] == '1') {
				visit[next_y][next_x] = visit[cur_y][cur_x] + 1;
				q.push(pair<int, int>(next_y, next_x));
			}
		}
	}

	return visit[N - 1][M - 1];

}

int main() {

	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) {
		cin >> map[i];
	}
	
	int result = bfs();
	cout << result << endl;

	return 0;
}