⚙️ 알고리즘 분류 : DFS+DP=메모이제이션
🔠 언어 : c++
🤫 힌트.
dp를 사용해야 한다. 그것도 방향 고려해서...!
✏️ 풀이.
이 문제의 포인트⭐️는 아래 3개다.
1) dp는 3차원 배열로 [방향][x좌표][y좌표] 이렇게 두어야 한다.
2) 단순 dfs가 아니라 dp를 사용해야 시간 초과가 안 생긴다.
3) dfs는 dp의 값이 갱신될 때만 돌아간다.
1)
같은 좌표를 여러 번 가더라도 방향에 따라 (직선 or 코너)로 다를 수 있다.
방향이 다른 점을 고려해서 3차원 배열로 방향까지 포함한다.
2)
dp는 해당 방향으로 해당 좌표에 갔을 때 누적되는 비용을 뜻한다.
dp의 값이 더 작은 값으로 갱신될 때만 업데이트 해주고 dfs 돌린다.
3)
같은 index 값을 가지는 dp의 값이 더 적을 경우에만 업데이트 한다.
dfs 문제 풀면 보통 visit 배열로 체크하는데, 여기선 체크할 필요가 없다.
이전에 방문했던 곳을 다시 가면, 같은 좌표인데 기존 비용에서 100원이 더 드니까 dfs가 돌아가지 않아서 상관 없다.
⚠️ 헤맨 부분.
dp[k][i][j]에서 k는 상하좌우 방향 4개를 나타낸다.
방향을 나타내는 숫자를 0~3으로 설정했는데, 바보 같이 초기화 할 때 k를 1~4로 설정해서 자꾸 틀렸다. 바부....
👩🏻💻 코드.
#include <string>
#include <vector>
#define MX 999999999
using namespace std;
// 0,2 -> 좌우, 1,3 -> 상하
// 상하와 좌우의 index끼리 더하면 짝수고
// 서로 교차해서 더하면 홀수다.(0+1=1)
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};
int arr[26][26];
int dp[4][26][26];
int sz, answer=MX;
bool ch(int x, int y){
if(x>=1 && x<=sz && y>=1 && y<=sz && !arr[x][y]) return true;
return false;
}
void dfs(int x, int y, int cost, int dir){
if(x==sz && y==sz){
answer=min(answer, cost);
return;
}
for(int i=0; i<4; i++){
int xx=x+dx[i], yy=y+dy[i];
if(ch(xx, yy)){
int new_cost=cost+100;
// 만약 현재와 다음이 서로 교차되는 방향이면 더했을 때 홀수다.
// 그리고 dir이 -1인 경우는 시작점인데,
//그때는 어딜가든 직선으로 가는 거니까 -1인 경우는 예외처리한다.
if((dir+i)%2==1 && dir!=-1) new_cost+=500;
// 여기가 포인트!!! DP 사용!!!
if(dp[i][xx][yy]>new_cost){
dp[i][xx][yy]=new_cost;
dfs(xx,yy,new_cost,i);
}
}
}
}
int solution(vector<vector<int>> board) {
sz=board.size();
for(int i=1; i<=sz; i++){
for(int j=1; j<=sz; j++) {
arr[i][j]=board[i-1][j-1];
// k는 0~3로 설정해두자! (dx, dy가 0~3이기 때문)
for(int k=0; k<4; k++) dp[k][i][j]=MX;
}
}
dfs(1,1,0,-1);
return answer;
}😎 후기.
꽤 여러 번 풀어봤는데, 풀 때마다 틀린다. dfs와 dp를 활용한 문제를 꽤 많이 마주한 편인데, 그 유형의 정석같은 느낌이다.
나의 깨달음 경과:
단순히 ch 배열로 해당 칸을 방문했는지만 체크하면 안 됨
-> 어느 방향에서 오든 해당 칸의 최소 비용을 고정하면 안 됨
-> 모든 방향을 고려해서, 어느 방향일 때의 최소 비용임을 저장해야 함
코테 준비하면 한 번 풀어볼만한 문제.
