백준 2178 미로 탐색

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 배열에 1 과 0 을 입력받고 1로만 이동 하며 끝점까지 이동하는데 지나야하는 최소의 칸 수를 찾는 문제이므로 bfs를 이용해서 풀면 해결되는 간단한 문제입니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <queue>

using namespace std;

int N,M;
int maze[101][101];
queue<pair<int, int>> q;
int nextx[4] = {1, 0, -1, 0};
int nexty[4] = {0, 1, 0, -1};
int visited[101][101];
int num = 1;

void bfs() {
	q.push(make_pair(0, 0));
	visited[0][0] = 1;
	while(!q.empty()) {
		int len = q.size();
		
		for(int i = 0; i < len; i++) {
			for(int j = 0; j < 4; j++) {
				int x = q.front().first + nextx[j];
				int y = q.front().second + nexty[j];
				
				if(x < 0 || x >= N || y < 0 || y >= M)
					continue;
				
				if(x == N-1 && y == M-1) {
					num++;
					return;
				}
				
				if(!visited[x][y] && maze[x][y] == 1) {
					visited[x][y] = 1;
					q.push(make_pair(x, y));
				}
			}
			q.pop();
		}
		num++;
	}
		
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> M;
	
	for(int i = 0; i < N; i++) {
		string str;
		cin >> str;
		for(int j = 0; j < M; j++)
			maze[i][j] = str[j] - '0';
	}
	
	bfs();
	cout << num;
}