[C++]白駿2178:探索迷宮
#include <iostream>
#include <queue>
using namespace std;
int N, M;
int map[101][101] = {0}; // 미로 입력
bool visited[101][101] = {false}; // 정점 방문 여부
queue<int> x, y, cnt; // 큐 2개 x, y, 칸 수 계산 - 길 탐색할 때 마다 거리 계산
int dx[4] = { 0, 0, -1, 1 }; // 상하좌우 좌표
int dy[4] = { -1, 1, 0, 0 };
bool check(int y, int x){ // y좌표를 먼저 해주는게 좋다고 한다.
if(y < 1 || y > N || x < 1 || x > M){
return false; // 좌표 범위 초과하면 갈 수 없음
} else if(map[y][x] == 0){
return false; // 벽이 있으면 이동 불가
} else if(visited[y][x]){
return false; // 이미 방문 했으면 이동 x
}
return true;
}
int main(int argc, char **argv){
scanf("%d %d",&N,&M);
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
scanf("%1d", &map[i][j]); // 숫자 1개씩 입력받기
}
}
x.push(1); y.push(1); // 첫 좌표 큐에 집어넣기
cnt.push(1); // 첫번째 칸
while(!y.empty()){
int yp = y.front(); y.pop(); // y 좌표
int xp = x.front(); x.pop(); // x 좌표
int cntp = cnt.front(); cnt.pop(); // 칸 수 세기
if(visited[yp][xp]){
continue; // 방문된 노드이면 패스
} else {
visited[yp][xp] = true; // 방문 체크
}
if(xp == M && yp == N){ // N * M 배열 N은 y, M은 x
// 도착점 도달
printf("%d", cntp);
break;
}
// 상하좌우 방문 - else if 사용 x
if(check(yp + dy[0], xp + dx[0])){ // y 먼저
x.push(xp + dx[0]);
y.push(yp + dy[0]);
cnt.push((cntp + 1));
}
if(check(yp + dy[1], xp + dx[1])){
x.push(xp + dx[1]);
y.push(yp + dy[1]);
cnt.push((cntp + 1));
}
if(check(yp + dy[2], xp + dx[2])){
x.push(xp + dx[2]);
y.push(yp + dy[2]);
cnt.push((cntp + 1));
}
if(check(yp + dy[3], xp + dx[3])){
x.push(xp + dx[3]);
y.push(yp + dy[3]);
cnt.push((cntp + 1));
}
}
return 0;
}
努力して解答するために、勉強しながら解決した問題.典型的なbfs問題と言える.この迷路問題は目的地を見つけると最短経路であることが保証されるため,bfsを用いる.
bfsが嫌いです.dfsの問題はコードが長すぎるからです.他の人のコードを確認すると、そんなに二次元配列を使うのではなく、pairを使って簡単に問題を解決して、ずっときれいに見えます.これからはこういう形で編む
#include <iostream>
#include <queue>
using namespace std;
string map[100];
int dis[100][100];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n,m;
queue<pair<int, int> > q;
void bfs(int x,int y) {
q.push(make_pair(x, y));
dis[x][y] = 1;
while (!q.empty()) {
x = q.front().first;
y = q.front().second;
q.pop();
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
&& dis[nx][ny] == 0 && map[nx][ny] == '1') {
q.push(make_pair(nx, ny));
dis[nx][ny] = dis[x][y] + 1;
}
}
}
}
int main(void) {
cin >> n>> m;
for (int i = 0; i < n; i++)
cin >> map[i];
bfs(0,0);
cout << dis[n - 1][m - 1];
}
출처: https://tooo1.tistory.com/163 [개발자 퉁이리]
ミス
グローバル変数が宣言され、同じ名前でゾーン変数が宣言されたため、グローバル変数に値が正しく挿入されませんでした.論理はすべて編んで、この1つのために1時間苦労して、ハハハ、もっと細かく編む必要があります.
Reference
この問題について([C++]白駿2178:探索迷宮), 我々は、より多くの情報をここで見つけました https://velog.io/@lamknh/C-백준-2178-미로탐색テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol