[C++] 백준 알고리즘 2178번 (미로 탐색)

문제

---

이번에 다뤄볼 문제는 2178번 문제 '미로 탐색'입니다.

미로 탐색 문제에서 연습해야하는 key-point는 BFS입니다.

 

BFS는 너비 우선 탐색을 뜻하는데요.

너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다.

문제를 살펴보면 N을 소인수분해 했을때 나타날 수 있는 인수중 가장 큰 값은 루트N입니다.

따라서, 2부터 루트N까지 for문을 돌면서 N을 나눌 수 있다면 계속 나눠주면 됩니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

 

코드(C++)

#include <iostream>
#include <stdio.h>
#pragma warning (disable:4996)
using namespace std;
 
    int n, m;
    int map[111][111];
    int visited[111][111];
 
    int queue[10000][2];
    int front = 0, rear = 0;
 
    int dirX[4] = { -1,1,0,0 };
    int dirY[4] = { 0,0,-1,1 };
 
int main() {
     
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
 
    int x = 1, y = 1;
    visited[x][y] = 1;
    queue[rear][0] = x; queue[rear++][1] = y;
 
    int xx = 0, yy = 0;
    while (front != rear) {
        x = queue[front][0]; 
        y = queue[front++][1];
 
        for (int k = 0; k < 4; k++) {
            xx = x + dirX[k];
            yy = y + dirY[k];
 
            if (map[xx][yy] == 0 || xx<0 || xx>n || yy<0 || yy>m) continue;
            if ((map[xx][yy] == 1 && visited[xx][yy] == 0) || (visited[xx][yy] > visited[x][y] + 1 && visited[xx][yy] != 0)) {
                visited[xx][yy] = visited[x][y] + 1;
                queue[rear][0] = xx; 
                queue[rear++][1] = yy;
            }
 
        }
 
    }
 
    cout << visited[n][m] << endl;

    return 0;
}