문제 조건

input

• 현재 보드의 상태 board
  • 3 ≤ board.size() ≤ 25

output

• n, m에 도착할 수 있는 최소 비용

문제 해석

• 경로 이동시 기본적으로, 100 추가
• 코너가 발생할 경우, 500 추가
• 막힌 경로 1, 가능한 경우 0

코드

#include <string>
#include <vector>
#include <climits>

using namespace std;

void dfs(int& answer, vector<vector<int>>& board, int x, int y, int cost, int dir) {
    
    if (cost >= answer) return;
    
    if (y==board[0].size()-1 && x==board.size()-1) {
        answer = min(cost, answer);
        return;
    }
    
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    
    for (int i=0; i<4; i++) {
        int nx = dx[i]+x;
        int ny = dy[i]+y;
        
        if (nx>=0 && ny>=0 && nx < board.size() && ny < board[0].size() && board[nx][ny]==0) {
            
            int next_cost = cost;        
            if ((x==0 && y ==0) || dir == i) next_cost += 100;
            else next_cost += 600;
    
            board[nx][ny] = 1;
            dfs(answer, board, nx, ny, next_cost, i);
            board[nx][ny] = 0;
        }
    }   
}

int solution(vector<vector<int>> board) {
    int answer = INT_MAX;
    board[0][0] = 1;
    dfs(answer, board, 0, 0, 0, -1);
    
    return answer;
}

• 80점으로 일부 케이스에 대해서 시간초과

• 시간 초과를 줄이기 위해, 메모제이션을 통해 일부 경로를 차단