[C++] 백준 1445번 : 일요일 아침의 데이트

 🔗 문제

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

 

✏️ 풀이

문제를 잘 읽어야 하므로 특. 별. 히 캡처를 해왔습니다. 

저는 노란 부분만 잘 읽으면 된다고 생각하고 난이도도 골4라고 생각됩니다. 

 

구현 문제는 정리를 하고 풉니다. 

 

[나는 무엇을 구현해야하는가?]

2차원 배열에서 출발지가 주어지고 '쓰레기칸', '쓰레기인접칸'을 최소로 밟고 목적지까지 도달하는 것.

출발지와 목적지가 주어져있고, 재방문 여부와 상관없이 가중치만 최소로 해야 한다. -> 다익스트라

 

이렇게 차분히 생각하면 알고리즘을 특정할 수 있고 문제가 쉬워집니다. 

 

[조금의 최적화]

특정 위치가 쓰레기 인접칸인지 확인하려고 매번 4방 탐색을 한다?

같은 칸을 여러 번 방문하는 다익스트라 특성상 비효율적입니다. 

쓰레기위치에서 사방탐색해 주어 미리 인접칸을 구합니다. 

저는 쓰레기 인접칸을 '#'로 바꾸어 빠르게 판단할 수 있도록 했습니다. 

 

 

💾  소스

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> pii;

const int MAX_N = 50 + 1;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

int N, M;

struct Node
{
    int trash, around;
    int x, y;
};

struct cmp
{
    bool operator()(const Node& a, const Node& b) const
    {
        if(a.trash >= b.trash) return a.around > b.around;
        return a.trash > b.trash;
    }
};

bool isValid(const int x, const int y)
{
    if(x<0 || y<0 || x>=N || y>=M)
        return false;
    return true;
}

int main()
{
    pii S, F;
    char grid[MAX_N][MAX_N];

    queue<pii> trash;
    priority_queue<pii> pq;

    cin >> N >> M;

    vector<vector<pii>> dp(N+1, vector<pii>(M+1, {1e9, 1e9}));

    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<M; ++j)
        {
            cin >> grid[i][j];
            if(grid[i][j] == 'F') F = make_pair(i, j);
            else if(grid[i][j] == 'S') S = make_pair(i, j);
            else if(grid[i][j] == 'g') trash.push({i, j});
        }
    }

    // 주변 위치 표시 #
    while(!trash.empty())
    {
        pii front = trash.front();
        trash.pop();

        for(int d=0; d<4; ++d)
        {
            int x = front.first + dx[d];
            int y = front.second + dy[d];

            if(!isValid(x, y) || grid[x][y] != '.') continue;

            grid[x][y] = '#';
        }
    }

    // 출발
    pq.push(S);
    dp[S.first][S.second] = {0, 0};
    while(!pq.empty())
    {
        pii top = pq.top();
        int nowX = top.first;
        int nowY = top.second;
        pq.pop();

        for(int d=0; d<4; ++d)
        {
            int x = top.first + dx[d];
            int y = top.second + dy[d];

            if(!isValid(x, y)) continue;

            int next_trash = dp[nowX][nowY].first + (grid[x][y] == 'g' ? 1 : 0 );
            int next_around = dp[nowX][nowY].second + (grid[x][y] == '#' ? 1 : 0);
            if(dp[x][y].first > next_trash ||
                (dp[x][y].first == next_trash && dp[x][y].second > next_around))
            {
                dp[x][y] = make_pair(next_trash, next_around);
                pq.push({x, y});
            }
        }
    }

    cout << (dp[F.first][F.second].first == 1e9 ? 0 : dp[F.first][F.second].first)
    << " " << (dp[F.first][F.second].second == 1e9 ? 0 : dp[F.first][F.second].second);


    return 0;
}