# [Gold II] 소가 길을 건너간 이유 7 [문제 링크](https://www.acmicpc.net/problem/14461) ## 문제 설명 <p>소가 길을 건너는 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.</p> <p>존의 농장에는 작은 정사각형 목초지가 N×N (3 ≤ N ≤ 100) 격자로 이루어져 있다. <a href="https://www.acmicpc.net/problem/14469">농장의 바깥에는 높은 울타리</a>가 있어서 소가 농장 밖으로 나갈 일은 없다. 이 농장에 사는 소 베시는 한 목초지에서 상하좌우로 인접한 다른 목초지로 이동할 수 있지만, 교통사고를 피하기 위해 차가 안 오는지 확인하고 길을 건너야 한다. 길을 건너는데는 T초 (0 ≤ T ≤ 1,000,000)가 걸린다.</p> <p>존이 베시에게 체스 대결을 신청했다. 베시는 북서쪽 끝에 있는 목초지에서 남동쪽 끝에 있는 존의 집으로 가야 한다. 길이 멀기 때문에 베시는 가는 도중에 배가 고파진다. 그래서 길을 세 번 건널 때마다 목초지에 있는 풀을 먹어야 한다. 존의 집에 도착할 때도 해당되지만, 출발할 때는 해당되지 않는다. 목초지마다 풀이 자란 정도가 달라서, 풀을 먹는데 걸리는 시간도 다르다.</p> <p>베시가 가능한 한 빨리 존의 집에 도착할 수 있도록 도와주자.</p> ## 입력 <p>첫 줄에 N과 T가 주어진다. 다음 N줄에는 목초지마다 풀을 먹는데 걸리는 시간이 N×N의 형태로 주어진다. 각각의 수는 모두 100,000 이하이다.</p> ## 출력 <p>베시가 존의 집까지 가는데 걸리는 최소 시간을 출력한다.</p> ## 풀이 minCost[x][y][cnt] 3차원 배열을 사용하는 기초적인 다익스트라 문제입니다. ``` c++ #include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; int minCost[100][100][3], board[100][100]; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; struct element { int x, y, cnt, cost; bool operator<(const element e) const { return cost > e.cost; } }; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, t; cin >> n >> t; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin >> board[i][j]; fill(&minCost[0][0][0], &minCost[99][99][3], INF); priority_queue<element> pq; pq.push({0, 0, 0, 0}); while(!pq.empty()) { auto [x, y, cnt, cost] = pq.top(); pq.pop(); if(cost>=minCost[x][y][cnt]) continue; minCost[x][y][cnt]=cost; for(int i=0;i<4;i++) { int nx = x+dx[i]; int ny = y+dy[i]; if(nx<0 || nx>=n || ny<0 || ny>=n) continue; int nCost = minCost[x][y][cnt] + (cnt+1==3 ? board[nx][ny] : 0) + t; if(minCost[nx][ny][(cnt+1)%3]>nCost) pq.push({nx, ny, (cnt+1)%3, nCost}); } } cout << *min_element(minCost[n-1][n-1], minCost[n-1][n-1]+3); } ```