백준 2178번 미로탐색

https://www.acmicpc.net/problem/2178

이 문제에서 도착지점에 도착할 수 있는 최소의 칸 수가 답이라하여, cmath 의 min 함수를 사용할 필요는 없다. 왜냐하면 특정 (n, m) 좌표에 도착할 때는 항상 최소값을 가지기 때문이다.

위의 사항을 주의하고 기본적인 dfs 알고리즘을 적용시키면 답을 도출시킬 수 있다.

#include <iostream>
#include <queue>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
int main()
{
    char map[101][101];
    int row, col, d[101][101] = {0, };
    int dx[4] = {0, -1, 0, 1};
    int dy[4] = {-1, 0, 1, 0};
    cin >> row >> col;
    
    for(int i = 0; i < row; ++i) {
        for(int j = 0; j < col; ++j) {
            d[i][j] = -1;
        }
    }
    
	for (int i = 0; i < row; ++i)
		cin >> map[i];
    
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    d[0][0] = 1;
    
    while (!q.empty()) {
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();
        
        if (curX == row -1 && curY == col - 1) {
            break;
        }
        
        for (int i = 0; i < 4; ++i) {
            int newX = curX + dx[i];
            int newY = curY + dy[i];
            
            if ((newX >= 0 && newX < row && newY >= 0 && newY < col) && map[newX][newY] != '0' && d[newX][newY] == -1) {
                q.push(make_pair(newX, newY));
                d[newX][newY] = d[curX][curY] + 1;
            }
            
        }
    }
    
    cout << d[row-1][col-1] << endl;
    return 0;
}