[BOJ] 2178. 미로 탐색

14607 단어 BFS알고리즘BFS

풀이

#include <iostream>
#include <stdio.h>
#include <queue>

using namespace std;

typedef struct point{
	int x;
	int y;
} point;

int N, M;
int is_visit[101][101];
int map[101][101];
int maze[101][101];
queue<point> Q;
int d_x[] = {0, 1, 0, -1};
int d_y[] = {1, 0, -1, 0};

int is_visitable(int x, int y);
void bfs(int x, int y);
point make_point(int x, int y);

int main(){
	cin >> N >> M;
	for (int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			scanf("%1d", &map[i][j]);
		}
	}
	bfs(1, 1);	
}

point make_point(int x, int y){
	point p;
	p.x = x; p.y = y;
	return p;
}

void bfs(int x, int y){
	is_visit[x][y] = 1;
	Q.push(make_point(x, y));
	maze[x][y] = 1;

	while(!Q.empty()){
		point p = Q.front();
		int x = p.x;
		int y = p.y;
		Q.pop();
		if(x == N && y == M){
			cout << maze[x][y] << endl;
			return;
		}
		for(int i = 0; i < 4; i++){
			int next_x = x + d_x[i];
			int next_y = y + d_y[i];
			if(is_visitable(next_x, next_y)){
				Q.push(make_point(next_x, next_y));
				is_visit[next_x][next_y] = 1;
				maze[next_x][next_y] = maze[x][y] + 1;
			}
		}
	}
}

int is_visitable(int x, int y){
	if(x >= 1 && x <= N && y >= 1 && y <= M && !is_visit[x][y] && map[x][y]) return 1;
	return 0;
}

전에 풀었던 것보다 코드는 간결해지고 문제 풀이 시간은 줄었다.

좋은 웹페이지 즐겨찾기