김로그 개발 잘 하고 싶다

2178번 미로 탐색



2178번 미로 탐색

(0, 0)에서 (N, M)까지 이동하는 최소 이동수를 구하는 문제이다. bfs로 문제를 풀 수 있다.

전체소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <queue>
using namespace std;

int N, M;
int map[100][100]={0,};
const int dx[]={-1,1,0,0};
const int dy[]={0,0,1,-1};
void bfs(int x, int y);

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

	map[0][0] = 2;
	bfs(0,0);

	printf("%d\n",map[N-1][M-1]-1);

	return 0;
}

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

	while(!q.empty()){
		x = q.front().first;
		y = q.front().second;
		q.pop();
		for(int k = 0 ; k < 4; k++){
			int nx = x + dx[k];
			int ny = y + dy[k];
			if(nx < 0 || nx > N-1 || ny < 0 || ny > M-1) continue;
			if(map[nx][ny] == 1){
				q.push(make_pair(nx,ny));
				map[nx][ny]=map[x][y]+1;
			}
		}
	}
}

reference