[BOJ/백준] 2178 - 미로탐색 (C++)

문제 링크 : https://www.acmicpc.net/problem/2178

문제 설명

1, 그래프에서 1은 이동가능, 0은 이동불가능
2. 인접한 칸으로만 이동가능
3. 시작점은 (0, 0) , 도착점은(N-1, M-1)으로 고정

Code

#include <iostream>
#include <string>
#include <deque>
using namespace std;


int N, M;
string board[101];
int visited[101][101];
int di[4] = {0, 0, 1, -1};
int dj[4] = {1, -1, 0, 0};
void input() {
    cin >> N >> M;
    for(int i = 0; i < N;i++) {
        cin >> board[i];
        fill(visited[i], visited[i] + M, 0);
    }

}
// void print() {
//     for(int i=0; i < N ; i ++) {
//         for(auto c : visited[i]) {
//             cout << c << ' ';
//         }
//         cout << endl;
//     }
// }
void solve() {
    deque<pair<int,int>> dq;
    dq.push_back(make_pair(0, 0));
    visited[0][0] = 1;
    while(!dq.empty()) {
        int ci = dq.front().first;
        int cj = dq.front().second;
        dq.pop_front();
        for(int k = 0; k<4 ; k++) {
            int ni = ci + di[k];
            int nj = cj + dj[k];
            if(ni < 0|| N <= ni || nj < 0 || M <=nj) {
                continue;
            }
            if(board[ni][nj] == '0') {
                // cout << ni << ' ' << nj;
                continue;
            }
            if(visited[ni][nj]) {
                continue;
            }

            dq.push_back(make_pair(ni, nj));
            visited[ni][nj] = visited[ci][cj] + 1;
        }
    }
}

int main() {
#ifdef LOCAL_DEBUG
    freopen("input.txt", "r", stdin);
#endif

    input();
    solve();
    // print();
    cout << visited[N-1][M-1];

    return 0;
}

• string으로 입력받았기 때문에 벽을 확인할 때, 0이 아닌 '0'을 확인했어야 했다.
• 좀더 mordern 하고 간결한 문법으로 풀 수 있었다.
• 아래는 좀더 모던하고 간결한 방법의 풀이
•  

#include <iostream>
#include <string>
#include <deque>
#include <vector>
using namespace std;

int N, M;
vector<string> board;
vector<vector<int>> visited;
int di[4] = {0, 0, 1, -1};
int dj[4] = {1, -1, 0, 0};

void input() {
    cin >> N >> M;
    board.resize(N);
    visited.assign(N, vector<int>(M, 0));
    for (int i = 0; i < N; ++i) {
        cin >> board[i];
    }
}


void solve() {
    deque<pair<int, int>> dq;
    dq.emplace_back(0, 0);
    visited[0][0] = 1;
    while (!dq.empty()) {
        auto [ci, cj] = dq.front();
        dq.pop_front();
        for (int k = 0; k < 4; ++k) {
            int ni = ci + di[k];
            int nj = cj + dj[k];
            if (ni < 0 || ni >= N || nj < 0 || nj >= M) {
                continue;
            }
            if (board[ni][nj] == '0' || visited[ni][nj]) {
                continue;
            }

            dq.emplace_back(ni, nj);
            visited[ni][nj] = visited[ci][cj] + 1;
        }
    }
}

int main() {
#ifdef LOCAL_DEBUG
    freopen("input.txt", "r", stdin);
#endif

    input();
    solve();
    // print();
    cout << visited[N-1][M-1] << endl;

    return 0;
}

1. vector와 vector<vector>를 사용하여 동적으로 할당하고 초기화.
2. auto를 사용하여 변수 타입 자동 추론.
3. emplace_back을 사용하여 객체를 직접 생성 및 삽입.
4. 범위 기반 for 루프를 사용하여 가독성 향상.
5. auto [ci, cj] = dq.front();를 사용하여 pair를 간단하게 언팩.