[틀림] 백준 11909 배열탈출 // 최단거리는 다익스트라(비용다름), 튜플사용법

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

 

* 개념

• 최단거리 알고리즘 비교
  • bfs 
    • 가중치가 같은 그래프
  • 다익스트라
    • 가중치가 다른 그래프

 

* 다익스트라 복습

• 느긋한 삭제
  • 중복된 정점(3)이 저장된경우, 건너뛰어버리기
  • for문 위에 코드 한줄 추가

#include <cstdio> 
#include <algorithm> 
#include <vector>
#include <queue>
using namespace std; 
int V, E, K, u, v, w; 
vector<pair<int, int>> adj[20001]; 
int dist[20001];
bool visited[20001];
const int INF = 987654321; 
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; 
int main(){
	scanf("%d %d %d", &V, &E, &K);
	fill(dist, dist + 20001, INF);
	for(int i = 0; i < E; i++){
		scanf("%d %d %d", &u, &v, &w);
		adj[u].push_back(make_pair(w, v)); 
	}
	pq.push(make_pair(0, K));
	dist[K] = 0; 
	while(pq.size()){ 
		int here = pq.top().second;
		int here_dist = pq.top().first;
		pq.pop();
		if(dist[here] != here_dist) continue;
		for(pair<int, int> there : adj[here]){
			int _dist = there.first;  
			int _there = there.second; 
			if(dist[_there] > dist[here] + _dist){
				dist[_there] = dist[here] + _dist; 
				pq.push(make_pair(dist[_there], _there));  
			}  
		}
	} 
	for(int i = 1; i <= V; i++){ 
		if(dist[i] == INF) puts("INF");
		else printf("%d\n", dist[i]); 
	}
	return 0; 
}
[출처] [알고리즘 강의] 8주차. 펜윅트리와 최단거리알고리즘(다익스트라, 플로이드워셜, 벨만포드)|작성자 큰돌

 

* 튜플사용법

• greater < vector 아님에 주의
• greater <tuple 바로 넣으면됨

priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,
   greater<tuple<int,int,int>>> pq;

• 꺼낼때는 get<index>(tuple)

auto cur = pq.top();
pq.pop();

int w = get<0>(cur);
int y = get<1>(cur);
int x=  get<2>(cur);

 

* 풀이

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;

int n;
int dist[2224][2224], a[2224][2224];
int INF = 987654321;
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, 
   greater<tuple<int, int, int>>> pq;

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr); cout.tie(nullptr);

   cin >> n;

   // 전체 dist 배열을 INF로 초기화 (n*n만큼 초기화해도 되지만 배열 크기 그대로 사용)
   fill(&dist[0][0], &dist[0][0] + 2224 * 2224, INF);

   for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
         cin >> a[i][j];
      }
   }

   // 시작점 초기화
   dist[0][0] = 0;
   pq.push({0, 0, 0});

   while (!pq.empty()) {
      auto [w, y, x] = pq.top();
      pq.pop();

      if (dist[y][x] != w) continue; // 느긋한 삭제

      // 동적 이웃 계산: 오른쪽과 아래쪽만 가능
      // 아래쪽 이동
      if (y + 1 < n) {
         int ny = y + 1, nx = x;
         int cost = 0;
         if (a[y][x] > a[ny][nx])
            cost = 0;
         else if (a[y][x] == a[ny][nx])
            cost = 1;
         else 
            cost = abs(a[y][x] - a[ny][nx]) + 1;
         if (dist[ny][nx] > dist[y][x] + cost) {
            dist[ny][nx] = dist[y][x] + cost;
            pq.push({dist[ny][nx], ny, nx});
         }
      }
      
      // 오른쪽 이동
      if (x + 1 < n) {
         int ny = y, nx = x + 1;
         int cost = 0;
         if (a[y][x] > a[ny][nx])
            cost = 0;
         else if (a[y][x] == a[ny][nx])
            cost = 1;
         else 
            cost = abs(a[y][x] - a[ny][nx]) + 1;
         if (dist[ny][nx] > dist[y][x] + cost) {
            dist[ny][nx] = dist[y][x] + cost;
            pq.push({dist[ny][nx], ny, nx});
         }
      }
   }
   
   cout << dist[n-1][n-1];
   return 0;
}

 

* 의문

• adj에 먼저 인접리스트를 넣었더니 메모리초과

vector<pair<int,int>> adj[2224][2224];
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,
   greater<tuple<int,int,int>>> pq;

void makeAdj() {
   for(int i=0;i<n;++i) {
      for(int j=0;j<n;++j) {
         if(i+1 <n)
            adj[i][j].push_back({i+1,j});
         if(j+1<n)
            adj[i][j].push_back({i,j+1});
      }
   }
}