경주로 건설

코드

[ DFS풀이 - 실패 ]

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1 ,-1, 0};
bool vis[30][30];
int cost[30][30];
int MAXSIZE;
int N;
void dfs(int y, int x, vector<vector<int>>& board, int status){
    if(y == N-1 and x == N-1){
        return;
    }
    for(int dir=0;dir<4;dir++)
    {
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        if(nx<0 or ny<0 or nx>=N or ny>=N) continue;
        if(vis[ny][nx] or board[ny][nx]) continue;
        int value=100;
        int sta=1;
        /* 비용 & 상태 검사 로직 */
        if(status == 1){
            if(dir==1 or dir==2) {
                value += 500;
                sta = 2;
            }
        }else if(status == 2){
            if(dir==1 or dir==2) sta = 2;
            else value += 500;                
        }else {
            if(dir==1 or dir==2) sta=2;
        }
        /* '현재 나온 비용'보다 '이미 기록한 비용'이 작으면 stop - 같을때 stop하면 안됨
           —> 왜냐하면 값은 같아도 현재까지 온 경로가 다르므로 영향을 줄 수 있음 */
        if(cost[ny][nx] < cost[y][x]+value) continue;
        cost[ny][nx] = cost[y][x] + value;
        vis[ny][nx] = true;
        dfs(ny, nx, board, sta);
        vis[ny][nx] = false;
    }
}
int solution(vector<vector<int>> board) {
    int ans;
    N = board.size();
    MAXSIZE = (N)*(N)*500;
    for(int i=0;i<N;i++)
        fill(cost[i], cost[i]+N, MAXSIZE);
    vis[0][0] = true;
    cost[0][0] = 0;
    // status=1이면 x축으로 이동중, status=2이면 y축으로 이동중, 0이면 초기값이니 100원 고정
    dfs(0,0,board,0);
    ans = cost[N-1][N-1];
    return ans;
}

• 결과
  • 14번 테스트케이스에 계속 실패가 떴음
  • 4방향 검사하는 dx[] / dy[]의 순서를 바꾸니 성공하긴함
    --> 안정적인 풀이는 아닌 것 같다
    (실제 구글링으로 찾은 dfs풀이들도 방향을 바꾸니 오답처리되었음)

[ BFS풀이 - 성공 ]

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#define F first
#define S second
using namespace std;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0 ,-1, 0};
int cost[2][30][30];
int MAXSIZE;
int N;
bool vis[30][30];

int solution(vector<vector<int>> board) {
    int ans;
    queue<pair<int,pair<int,int>>> q;
    N = board.size();
    MAXSIZE = (N)*(N)*500;
    for(int i=0;i<2;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
                cost[i][j][k] = MAXSIZE;
    q.push({0,{0,0}});
    q.push({1,{0,0}});
    cost[0][0][0] = 0;
    cost[1][0][0] = 0;
    vis[0][0] = true;
    while(!q.empty())
    {
        auto cur = q.front(); q.pop();
        for(int dir=0;dir<4;dir++)
        {
            int ny = cur.S.F + dy[dir];
            int nx = cur.S.S + dx[dir];
            int pdir = cur.F;
            if(ny<0 or nx<0 or ny>=N or nx>=N) continue;
            if(board[ny][nx]) continue;
            int ndir=dir%2; // 0=y축, 1=x축
            if(ndir == pdir){
                if(cost[ndir][ny][nx] > cost[pdir][cur.S.F][cur.S.S]+100){
                   cost[ndir][ny][nx] = cost[pdir][cur.S.F][cur.S.S] + 100;
                    q.push({ndir,{ny,nx}});
                }
            }else{
                if(cost[ndir][ny][nx] > cost[pdir][cur.S.F][cur.S.S]+600){
                   cost[ndir][ny][nx] = cost[pdir][cur.S.F][cur.S.S] + 600;
                    q.push({ndir,{ny,nx}});
                }
            }
        }
    }
    ans = min(cost[0][N-1][N-1], cost[1][N-1][N-1]);
    return ans;
}

• 결국 다른사람의 풀이를 참조함
• 해당 문제의 취지는 DFS보다는 BFS가 맞다고 한다
  --> 최소 비용을 구하는 문제라서
• 핵심
  • 메모제이션 + BFS를 이용한 풀이
  • 같은 좌표라도 어떤 방향에서의 최대값인지 기록해야 함
    --> cost를 3차원 배열로 지정
    ( cost[dir][y][x])
• 느낀 점
  • 최소 비용을 구하는 문제는 DFS보다는 BFS를 사용하자
  • 메모제이션을 할 때 방향성이 있다면 방향을 고려하자
    cost[dir][y][x]