백준11607 - Grid

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

11607번: Grid

다익스트라를 이용하여 푼 문제이다. 왼쪽 맨 위에서 오른쪽 맨 아래까지 최소 몇 번 만에 이동하는지 구하는 문제이다.

bfs를 이용하여 풀려고 하였는데 방문했던 곳을 재방문해야 되는 경우가 있어서 다익스트라를 이용하는 것이 편하였다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#define MAX 501
using namespace std;

int n, m;
string s;
int mat[MAX][MAX] = { 0, };
int cost[MAX][MAX] = { 0, };

int dx[] = { 1, -1, 0 , 0 };
int dy[] = { 0, 0, 1, -1 };

void dijkstra() {
    queue<pair<int, int>> q;
    q.push(pair<int, int>(1, 1));
    cost[1][1] = 0;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        int temp = mat[x][y];

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i] * temp;
            int ny = y + dy[i] * temp;
            if (1 <= nx && nx <= n && 1 <= ny && ny <= m) { //유효 범위이고
               if (cost[nx][ny] > cost[x][y] + 1) { //현재 도달하는 곳에 비용보다 갱신되는 비용이 작으면 비용 갱신
                   cost[nx][ny] = cost[x][y] + 1;
                    q.push(pair<int, int>(nx, ny));
               }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 1; j <= m; j++) {
            mat[i][j] = s[j - 1] - '0';
            cost[i][j] = 987654321;
        }
    }

    dijkstra();

    if (cost[n][m] == 987654321) {
        cout << "IMPOSSIBLE";
    }
    else {
        cout << cost[n][m];
    }
}