[백준] 2645 : 회로배치

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

문제 분석

 정리하자면 격자 공간에서 각 격자마다 이동비용이 존재할 때 특정 두 지점을 잇는  최소 비용을 구하는 문제이다. 격자의 한변의 크기인 N이 50보다 작은 수이기 때문에 단순한 다익스트라로도 해결가능하다.

문제 해결 전략

 우선 각 격자마다 비용을 입력으로 들어오는 회로를 통해 구해내고 다익스트라를 수행한 뒤 간단한 경로 추적까지만 구현하면 된다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

//문제분석
//격자에서 격자마다 비용이 존재할 때 특정 두 지점사이의 최소 비용 거리 구하기
//단순한 다익스트라문제
//  (V : N^2 = 2500, E=2*N*(N-1)=2N^2=5000, O(vlogE)=2500*12=3E4)
//각 격자를 노드로 엣지의 비용은 도착지의 비용
//=====================================================================
//해결전략
//1. N^2의 비용 맴 구하기
//2. 단순 다익스트라
//=====================================================================
//필요자료형
//변수
//vector<vector<int>> cost : 각 격자별 이동 cost
//vector<vector<int>> dist : 각 격자별 최소 비용
//priority_queue<int> : 다익스타룡 힙
//함수
//바로 구현

int N,K,M;
const int MAXV=150001; 

struct POINT
{
    POINT() : x(0), y(0) {};
    POINT(int _x, int _y) : x(_x), y(_y) {};
    bool IsVallid(){
        if (x>N || x<1 || y>N || y<1) return false;
        return true;
    }

    vector<POINT> GetAdjacentPoints(){
        vector<POINT> adjacentPoints;
        const static int d[4][2] ={
            {1,0},
            {-1,0},
            {0,1},
            {0,-1},
        };
        for (size_t i = 0; i < 4; i++) {
            POINT adjacentPoint = POINT(x+d[i][0],y+d[i][1]);
            if (adjacentPoint.IsVallid()) adjacentPoints.push_back(adjacentPoint);
        }
        return adjacentPoints;
    }

    friend ostream& operator<<(ostream& os, const POINT& pt){
        os << pt.x << " " << pt.y << " ";
        return os;
    }

    bool operator==(const POINT& otherPoint) {return (x==otherPoint.x)&&(y==otherPoint.y);}

    int x;
    int y;
};

int main()
{
    cin >> N;
    int x, y;
    cin >> x >> y;
    POINT P=POINT(x,y);
    cin >> x >> y;
    POINT Q=POINT(x,y);
    cin >> K >> M;
    vector<vector<int>> cost= vector<vector<int>>(N+1, vector<int>(N+1, 1));
    vector<vector<int>> dist= vector<vector<int>>(N+1, vector<int>(N+1, MAXV));

    auto cmp = [] (pair<int,POINT> a, pair<int,POINT> b)
    {
        return a.first > b.first;
    };

    priority_queue<pair<int,POINT>,vector<pair<int,POINT>>, decltype(cmp)> heapq(cmp);
    
    for (size_t i = 0; i < M; i++)
    {
        int circuitSize;
        cin >> circuitSize;
        int curx,cury,prevx,prevy;

        cin >> prevx >> prevy;
        for (size_t j = 0; j < circuitSize-1; j++)
        {
            cin >> curx >> cury;

            for (int x = prevx; x != curx; (curx>=prevx) ? x++ : x--) cost[x][prevy]=K;
            for (int y = prevy; y != cury; (cury>=prevy) ? y++ : y--) cost[prevx][y]=K;

            prevx=curx;
            prevy=cury;
        }
        cost[curx][cury]=K;
    }
    
    heapq.push(make_pair(cost[P.x][P.y],P));
    int curDist;
    POINT curPoint,nxtPoint;

    while(!heapq.empty()){
        tie(curDist,curPoint)=heapq.top();
        heapq.pop();

        if (dist[curPoint.x][curPoint.y]<=curDist) continue;
        dist[curPoint.x][curPoint.y]=curDist;
        if (curPoint==Q) break;

        for (const auto& nxtPoint : curPoint.GetAdjacentPoints())
        {
            int nxtDist=curDist+cost[nxtPoint.x][nxtPoint.y];
            if (dist[nxtPoint.x][nxtPoint.y]>nxtDist) heapq.push(make_pair(nxtDist,nxtPoint));
        }
    }

    vector<POINT> fullPath;
    fullPath.push_back(Q);
    curPoint=Q;
    while(!(curPoint==P)){
        for (auto nxtPoint : curPoint.GetAdjacentPoints())
        {
            if (dist[nxtPoint.x][nxtPoint.y]==dist[curPoint.x][curPoint.y]-cost[curPoint.x][curPoint.y]){
                curPoint=nxtPoint;
                fullPath.push_back(curPoint);
                break;
            }
        }
    }

    vector<POINT> turnPoints;
    turnPoints.push_back(P);
    for (int i = fullPath.size()-1; i >=0 ; i--)
        if (turnPoints.back().x!=fullPath[i].x && turnPoints.back().y!=fullPath[i].y) turnPoints.push_back(fullPath[i+1]);
    turnPoints.push_back(Q);
    
    cout << dist[Q.x][Q.y] << "\n";
    cout << turnPoints.size() << " ";
    for (auto pt : turnPoints) cout << pt;
}