✅ LV.3
📌 2020 카카오 인턴십
✏️ 1차 솔루션
DFS 로 풀이
🚨 trouble
시간초과 발생
최단경로를 찾는 게 아니라 최소비용을 찾는 것이고 그렇다고 코너를 돌 때 가중치가 부여되기 때문에 모든 경우의 수를 고려해야 함
하지만, 왔던 길을 되돌아가는 경우는 배제해야 하기 때문에 굳이 DFS 를 쓸 필요가 없고 시간 낭비만 하므로 BFS 를 사용해야함
✏️ 최종 솔루션
⭐️ 다익스트라
⭐️ 각 칸에 도달했을 때, 현재까지의 거리, 현재 방향, 현재까지 코너를 돈 횟수를 저장하면서 최소비용을 탐색하기 위해 하나의 struct 로 관리
⭐️ 최소비용을 갱신해나가기 위해 3차원 배열로 각 (x, y) 위치의 상하좌우 비용을 저장할 수 있도록 구현
⭐️ 우선순위 큐로 현재까지의 거리 작은 순으로 정렬
- 최소비용 갱신을 위한 배열 초기화
(0, 0)부터 각 위치에서 갈 수 있는 상하좌우 방향 노드 저장하면서(n-1, n-1)에 도달할 때까지 탐색
1) 상하좌우에서 갈 수 있는 위치 중에 현재 방향과 같을 경우와 다를 경우를 나누어 현재 위치를 거쳐 다음 위치까지 가는데 드는 비용 계산
2) 다음 위치의 상하좌우 각 방향에 저장된 비용이 1 에서 계산한 비용보다 크면 갱신하고 아니면 continue
3) 다음 위치가 현재 위치의 방향과 다르면 코너 돈 횟수 추가해서 큐에 push(n-1, n-1)의 상하좌우에 저장된 최소비용 중에 가장 작은 값이 answer
❗️ 어느 방향으로 현재 노드에 도달했는지는 비용에 영향을 미치기 때문에 현재 노드까지 도달하는 비용을 방향 별로 나누어서 갱신해야 함
ex) (a, b) 에 도달할 때 다음 3가지 경우가 있다면
1) 왼쪽 방향에서 현재 위치로 도착했을 때의 비용 1500
2) 이전에 왼쪽 방향에서 현재 위치로 도착했을 때 저장된 비용이 1000
3) 윗쪽 방향에서 현재 위치로 도착했을 때의 비용이 3000 이지만 윗쪽 방향에서 들어온 적이 없을 때
왼쪽 방향에서 들어온 경우는 이전에 들어온 비용보다 크기 때문에 더 이상 왼쪽 방향으로 진행하지 않도록 우선순위 큐에 Push 하지 않음
하지만 윗쪽 방향에서 들어온 경우는 3가지 경우 중에 가장 큰 비용을 갖음에도 불구하고 윗쪽 방향에서 들어온 것이 처음이기 때문에 현재 위치의 윗쪽 방향 visit 값에 갱신하고 현재 위치를 거쳐 계속 탐색하도록 우선순위 큐에 push
📌 self feedback
이 정도면 경로 찾기 문제는 DFS 가 아니라 BFS 사용하는 건 국룰인듯..
진행방향이 최소비용에 영향을 미치기 때문에 현재 위치의 최소비용을 현재 위치에 갱신하는 것이 아니라 현재 위치에 대한 상하좌우 공간을 만들어 3차원 배열로 갱신해나가는 것이 관건
✏️ 최종 code
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct node {
int x;
int y;
int dist;
int cnt; // 방황전환횟수
int dir;
};
struct cmp {
bool operator()(node n1, node n2) {
return n1.dist>n2.dist;
}
};
int visit[26][26][4];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
vector<vector<int>> bd;
priority_queue<node,vector<node>,cmp> pq;
void bfs() {
pq.push({0,0,0,0,-1});
for(int i=0;i<4;i++) {
visit[0][0][i]=0;
}
while(!pq.empty()) {
int x=pq.top().x;
int y=pq.top().y;
int d=pq.top().dist;
int c=pq.top().cnt;
int dir=pq.top().dir;
pq.pop();
if(x==bd.size()-1 && y==bd.size()-1) continue;
for(int i=0;i<4;i++) {
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<0 || nx>=bd.size() || ny<0 || ny >=bd.size()) continue;
if(bd[nx][ny]==1) continue;
int nc;
if(dir==-1 || dir==i) nc=100*(d+1)+500*c;
else if(dir!=i) nc=100*(d+1)+500*(c+1);
if(visit[nx][ny][i]>nc) visit[nx][ny][i]=nc;
else continue;
if(dir==-1 || dir==i) pq.push({nx,ny,d+1,c,i});
else if(dir!=i) pq.push({nx,ny,d+1,c+1,i});
}
}
}
int solution(vector<vector<int>> board) {
bd=board;
for(int i=0;i<bd.size();i++) {
for(int j=0;j<bd.size();j++) {
for(int k=0;k<4;k++) {
visit[i][j][k]=1e9;
}
}
}
bfs();
int answer = 1e9;
for(int i=0;i<4;i++) {
answer=min(answer,visit[bd.size()-1][bd.size()-1][i]);
}
return answer;
}