[C++] BOJ 2178번: 미로 탐색

문제

1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 나타낸다.

(1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소 칸의 수를 구하는 프로그램 작성하시오.

 

입력 1

4 6
101111
101010
101011
111011

출력 1

15

코드

#include<iostream>
#include<queue>
#include<algorithm>
#define MAX 101

using namespace std;

int MAP[MAX][MAX];
int visited[MAX][MAX];
int dist[MAX][MAX];
int arrow[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int N, M;
pair<int, int> startP, endP;

queue < pair<int, int>> Q;

void BFS() {
    
    Q.push(make_pair(startP.first, startP.second));

    dist[startP.first][startP.second]++;
    visited[startP.first][startP.second] = 1;

    while (!Q.empty()) {
        int y = Q.front().first;
        int x = Q.front().second;
        Q.pop();
        //좌우위아래 탐색
        for (int i = 0; i < 4; i++) {
            int ny = y + arrow[i][0];
            int nx = x + arrow[i][1];


            if ((nx >= 0 &&nx < M) && (ny >= 0 && ny < N)
                && MAP[ny][nx] == 1 &&!visited[ny][nx]) {
                visited[ny][nx] = 1;
                Q.push(make_pair(ny, nx));
                dist[ny][nx] = dist[y][x] + 1;
            }
        }
    }
    cout << dist[endP.first-1][endP.second-1];
}


void input() {
    string num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        for (int j = 0; j < M; j++) {
            MAP[i][j] = num[j]-'0';
        }
    }
}

int main() {

    cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

    int tmp;
    cin >> N>>M;
    startP = make_pair(0, 0);
    endP = make_pair(N, M);
    
    input();
    BFS();

    return 0;
}

 

*간단한 해설*

저 input 함수에서 cin을 통해 MAP을 받아옵니다.

주의할 점은 한 줄당 붙어있는 상태로 받아와서 cin으로 받은 다음 끊어서 저장해주어야합니다.

void input() {
    string num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        for (int j = 0; j < M; j++) {
            MAP[i][j] = num[j]-'0';
        }
    }
}

string으로 받은 다음 string에서 인자로 접근해주면 char 형이여서 char형을 int로 바꾸려면 '0'의 숫자를 빼주면 됩니다.

그런다음 BFS 탐색을 통해 최단 경로를 찾아주면 되는데 BOJ 6087번 레이저 통신과 문제가 매우 흡사합니다.

https://dana3711.tistory.com/90

[C++] BOJ 6087번: 레이저 통신

다만 다른점은 목표 지점까지 가는데 걸리는 비용을 출력해야한다는 점입니다. 따라서

if ((nx >= 0 &&nx < M) && (ny >= 0 && ny < N)&& MAP[ny][nx] == 1 &&!visited[ny][nx]) 
{
    visited[ny][nx] = 1;
    Q.push(make_pair(ny, nx));
    dist[ny][nx] = dist[y][x] + 1;
}

4방향 탐색을 할때 만약 맵 안에 있고((nx >= 0 &&nx < M) && (ny >= 0 && ny < N)), 그 칸이 이동할 수 있는 칸이라면(MAP[ny][nx] == 1) 해당 칸을 방문하지 않았을 때

해당 칸으로 자리를 이동하고 가는 비용을 +1 해줍니다.

 

 

 

 

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*