[Lev.3] 경주로 건설

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

2. 접근 방법

1. dfs 혹은 bfs로 풀 수 있다. 나는 재귀 연습을 위해 dfs를 돌렸지만, 위 문제의 경우 직전에 이동한 방향을 저장해야 하기 때문에 dfs함수를 두 번돌려야 했다.(아래로 시작하는 경우, 위로 시작하는 경우)

=> 최단 경로 나오면 일단 bfs로 푸는 연습을 하자

 

 

3. 처음 알았던 부분 & 실수한 부분 

 

1. fill함수 사용해서 2차원 배열 일부분만 초기화 하는 법( 이 문제에선 가운데 부분 값을 초기화시킴)

   - fill(&arr[0][0], &arr[MAX - 5][MAX - 3], 7);

 

2. 실패 원인 파악

https://keykat7.blogspot.com/2019/10/blog-post.html.

[백준] 실패 원인 - 틀렸습니다, 시간 초과, 메모리 초과, 출력 초과, 런타임 에러, 컴파일 에러

 

4. 코드 

#include <vector>
#include <iostream>
#define MAX 987654321
using namespace std;
int N;
vector<vector<int>> Board; 
pair<int, int> d[4] = {{-1,0},{0,1},{1,0},{0,-1}}; //상하좌우 순
int dp[26][26]; //(r,c)까지 도착했을 때, 만들 수 있는 최소 비용 저장

void go(int r, int c, bool dir) {//dir: 상하 방향이면 0,좌우방향이면 1
    if( r == N-1 && c == N-1) {
        return;
    }
    for( int i = 0; i< 4; i++) {
        int nr = r + d[i].first;
        int nc = c + d[i].second;
        if( nr < 0 || nr >=N || nc <0 || nc >=N || Board[nr][nc] == 1) continue; 
             if( (i%2 != dir) && (dp[nr][nc] > dp[r][c] + 600) ) {
                dp[nr][nc] = dp[r][c] + 600;
                go(nr,nc,i%2);
            }
            else if ( (i%2 == dir) && (dp[nr][nc] > dp[r][c] + 100)) {
                dp[nr][nc] = dp[r][c] + 100;           
                go(nr,nc,i%2);
            }
       }
}

int solution(vector<vector<int>> board) {
    N = board.size();
    int ans = MAX;
    Board = board;
    //(1,0)으로 가는 dfs 시작
    if(Board[1][0] == 0) {
      fill(&dp[0][0],&dp[25][25],MAX);
       dp[0][0] = 0;
       dp[1][0] = 100;
        go(1,0,0);
        ans  = min(ans, dp[N-1][N-1]);
    }
    //(0,1)로 가는 dfs 시작 ( 새로운 dfs가 시작되므로 dp배열 초기화 )
    if ( Board[0][1] == 0) {
        fill(&dp[0][0],&dp[25][25],MAX);
        dp[0][0] = 0;
        dp[0][1] = 100;
        go(0,1,1);
        ans = min(ans,dp[N-1][N-1]);
    }
    return ans;
}