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

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

2178번: 미로 탐색

[풀이]

bfs알고리즘을 이용하여 풀었다.

visited배열에 해당 칸이 출발지로부터 몇번째 칸인지 저장하면서 반복문을 돌리고, 목적지인 (N,M)에 도착하면 bfs함수에서 빠져나오면 된다.

이때 visited[N][M]이 (1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소의 칸 수이다.

 

#include <iostream>
#include <queue>
#include <cstdio>//scanf
using namespace std;

struct Pos {
	int x, y;//좌표
};

int N, M;
int Maze[101][101];
int visited[101][101] = { 0, };
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };

void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &Maze[i][j]);//붙어있는 수 중 하나만 입력
		}
	}
}

void bfs(int startx, int starty) {
	queue<Pos>q;
	visited[startx][starty] = 1;
	q.push({ startx,starty });
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		if (x == N - 1 && y == M - 1)
			return;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			//미로 범위 확인
			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
				continue;
			if (Maze[nx][ny] == 1 && visited[nx][ny] == 0) {
				visited[nx][ny] = visited[x][y] + 1;
				q.push({ nx,ny });
			}
		}
	}
}

void solution() {
	input();
	bfs(0, 0);
	cout << visited[N - 1][M - 1] << endl;
}

int main() {
	solution();
	return 0;
}