1261번

1261번 - 알고스팟

처음에는 너무 단순하게, 다른 많은 문제들에서 처럼 map 에서의 이동하는데 가중치가 없다고 생각해서,

BFS로 풀 수 있지 않을까 했지만..

벽을 최소한으로 뚫고 가야 하기 때문에, 벽이 막혀있을 때와 막혀있지 않을 때 가중치를 줘서 풀어야 했다.

즉 움직일 때, 최소한 벽을 뚫지 않아도 되는 쪽으로 움직이는게 좋다는 뜻이었다.

따라서 벽을 파야할때는 간선의 가중치를 1로, 그냥 움직일 수 있을 때는 0으로 두고 (즉 그냥 입력값을 그대로 사용)

다익스트라 알고리즘으로 마지막까지의 값을 구했다.

<정답 코드 - priority queue 사용>

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int map[101][101];
int dist[101][101];
const int INF = 987654321;
int main()
{
    int M, N;
 
    scanf("%d %d", &M, &N);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            dist[i][j] = INF;
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        char t[101];
        scanf("%s", &t);
        for (int j = 0; j < M; j++)
        {
            map[i][j] = t[j] - '0';
        }
    }
 
    priority_queue<pair<int,pair<int, int>>> pq;
    dist[0][0] = 0;
    pq.push({ 0, { 0,0 } });
 
    while (!pq.empty())
    {
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        int cost = -pq.top().first;
        pq.pop();
 
        if (cost > dist[x][y]) { continue; }
 
        for (int d = 0; d < 4; d++)
        {
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                int w = map[nx][ny];
                if (dist[nx][ny] > cost + w)
                {
                    dist[nx][ny] = cost + w;
                    pq.push({ -dist[nx][ny],{ nx,ny } });
                }
            }
        }
    }
 
    printf("%d\n", dist[N - 1][M - 1]);
 
 
    return 0;
}

<정답 코드 - priority queue 사용X>

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int map[101][101];
int dist[101][101];
bool visited[101][101];
const int INF = 987654321;
int main()
{
    int M, N;
 
    scanf("%d %d", &M, &N);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            dist[i][j] = INF;
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        char t[101];
        scanf("%s", &t);
        for (int j = 0; j < M; j++)
        {
            map[i][j] = t[j] - '0';
        }
    }
    dist[0][0] = 0;
    while (true)
    {
        int x,y;
        int smallest = INF;
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (!visited[i][j] && dist[i][j]<smallest)
                {
                    x = i;
                    y = j;
                    smallest = dist[i][j];
                }
            }
        }
 
        if (smallest == INF)
        {
            break;
        }
 
        visited[x][y] = true;
 
        for (int d = 0; d < 4; d++)
        {
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (dist[nx][ny] > smallest + map[nx][ny])
                {
                    dist[nx][ny] = smallest + map[nx][ny];
                }
            }
        }
    }
 
    printf("%d\n", dist[N - 1][M - 1]);
 
 
    return 0;
}