<div id="readability-page-1" class="page"><article><header><time datetime="October 15, 2016">October 15, 2016</time><a rel="tag" href="/tags#bfs">#bfs</a> <a rel="tag" href="/tags#백준온라인저지">#백준온라인저지</a> </header><section><a href="https://www.acmicpc.net/problem/2178" target="_blank" rel="noopener">2178번 미로 탐색</a>
(0, 0)에서 (N, M)까지 이동하는 최소 이동수를 구하는 문제이다. bfs로 문제를 풀 수 있다.
전체소스코드
<div data-language="cpp"><pre><code>#include &lt;cstdio&gt;
#include &lt;queue&gt;
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",&amp;N,&amp;M);
	for(int i = 0 ; i &lt;N ; i++){
		for(int j = 0 ; j &lt; M ; j++){
			scanf("%1d",&amp;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&lt;pair&lt;int, int&gt; &gt; 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 &lt; 4; k++){
			int nx = x + dx[k];
			int ny = y + dy[k];
			if(nx &lt; 0 || nx &gt; N-1 || ny &lt; 0 || ny &gt; M-1) continue;
			if(map[nx][ny] == 1){
				q.push(make_pair(nx,ny));
				map[nx][ny]=map[x][y]+1;
			}
		}
	}
}</code></pre></div>
<hr>
<h2>reference</h2>
<ul>
<li><a href="https://www.acmicpc.net/problem/2178" target="_blank" rel="noopener">2178번 미로 탐색</a></li>
<li><a href="https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89" target="_blank" rel="noopener">위키피디아 너비 우선 탐색</a></li>
</ul></section><hr></article></div>

Kimlog RSS Feed

KIM, WOOJUNG

2178번 미로 탐색
(0, 0)에서 (N, M)까지 이동하는 최소 이동수를 구하는 문제이다. bfs로 문제를 풀 수 있다.
전체소스코드
#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
2178번 미로 탐색
위키피디아 너비 우선 탐색

2178번 미로 탐색

댓글