[백준] 2178 미로 탐색

백준2178링크

NxM크기의 미로
(1,1)에서부터 (N,M)까지의 거리

입력

N, M(2 ≤ N, M ≤ 100)
N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력

출력

첫째 줄에 지나야 하는 최소의 칸 수 (항상 도착위치로 이동할 수 있는 경우만 입력으로 주어짐)

풀이

목적지까지의 최소 거리를 구하는 문제이기때문에 BFS로 접근
큐를 이용한 BFS코드를 사용하여 풀이하였는데, 거리를 계산하는 과정에서 조금 더 신경써야함

route라는 이차원 배열을 사용하여 첫 시작점은 거리가 1, 그 다음은 이전 값의+1씩 저장되도록 설정
visited 이차원 배열은 각 위치를 방문했는지를 확인

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>

#define MAXN 101

using namespace std;

int N, M;
int miro[MAXN][MAXN] = { 0, };

//방향 배열
int dx[4] = { 0,0, - 1,1 };
int dy[4] = { -1,1,0,0 };

int visited[MAXN][MAXN] = { 0, }; //방문 확인
int route[MAXN][MAXN] = { 0, }; //시작점부터의 거리 저장

void BFS(int x, int y) {

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

	visited[x][y] = 1;
	route[x][y] = 1; 	//처음 위치의 경우 거리 1로 설정

	while (!q.empty()) {
		int cx = q.front().first;
		int cy = q.front().second;

		q.pop();

			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
					int ny = cy + dy[i];

				if (nx < 0 || nx >= N || ny < 0 || ny >= M) { //미로 벗어나는 경우
					continue;
				}
				else {
					if (miro[nx][ny] == 1 && visited[nx][ny]==0) {
						q.push(make_pair(nx, ny));
						visited[nx][ny] = 1; //방문한 경우
						route[nx][ny] = route[cx][cy] + 1; //이전 위치(큐에서 꺼낸 cx,cy)부터 한 칸 더 온 경우이기 때문에

					}
					else {
						continue;
					}
				}
			}

	
	}
	return;

}


int main() {

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		
		for (int j = 0; j < M; j++) {
			miro[i][j] = (s[j]-'0');//문자열 숫자로 변환
		}
	}

	BFS(0, 0);

	cout << route[N - 1][M - 1];

	return 0;
}