문제
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
해결 방법
DFS보다 BFS가 개인적으로 코드가 더 복잡하게 느껴져서 그런지
DFS로 풀 수 있는 문제는 무조건 DFS로 풀었더니 BFS로 푼 문제가 없어서 참고할 코드가 없었다...
BFS 개념도 다시 찾아보고 결국 코드도 구글링 하긴 했다. 앞으로는 무조건 내 힘으로만 풀 수 있길..
이 코드에서 가장 중요한 부분은 25, 54번째 줄인 것 같다.
미로를 int형으로 받는데 공백이 없이 들어오기 때문에 char형으로 선언하고 %s나 %c로 받는 방법도 있겠지만
%1d로 받음으로써 배열 한 칸에 숫자 하나씩 저장되게 하는 방법을 사용하였다.
그리고 (1, 1)에서 (n, m)으로 가는 최단 경로를 찾아야 하기 때문에 vist[nx][ny] = 1이 아니라
이전까지 몇 개의 칸을 지나왔는지가 중요하기 때문에 이전 칸에서 계속 값을 1씩 증가시켜 줘야 한다는 것이 중요⭐
내 코드(C++)
/*[2178] 미로 탐색*/
/*https://www.acmicpc.net/problem/2178*/
/*BFS*/
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int n, m;
int visit[101][101] = { 0, };
int maze[101][101] = { 0, };
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
void bfs(int x, int y);
int main(void)
{
cin >> n >> m;
// input maze, start with (1, 1)
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%1d", &maze[i][j]); // 1d!!
}
}
bfs(1, 1);
cout << visit[n][m] << endl;
}
void bfs(int x, int y)
{
queue<pair<int, int> >q;
q.push(make_pair(x, y));
visit[x][y] = 1; /*visited*/
while (!q.empty()) {
x = q.front().first;
y = q.front().second;
q.pop();
// east, north, west, south
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (0 < nx && nx <= n && 0 < ny && ny <= m) {
// if not visited and can pass
if (visit[nx][ny] == 0 && maze[nx][ny] == 1) {
q.push(make_pair(nx, ny));
visit[nx][ny] = visit[x][y] + 1;
}
// not visited and cannot pass
else if (visit[nx][ny] == 0) {
visit[nx][ny] = -1;
}
}
}
}
}
반응형
'Baekjoon > BFS' 카테고리의 다른 글
[10451] 순열 사이클(C++) (0) | 2020.01.10 |
---|---|
[1260] DFS와 BFS(C++) (0) | 2019.09.15 |
[1697] 숨바꼭질(C++) (0) | 2019.09.15 |
[10026] 적록색약(C++) (0) | 2019.09.15 |
[2583] 영역 구하기(C++) (0) | 2019.09.14 |