[프로그래머스] 2020 카카오 인턴십 경주로 건설

 

2020 카카오 인턴십 [카카오 인턴]  경주로 건설

 

프로그래머스

 

 

 

---

탐색 기법 : DFS

목적지 도달까지 경로비용을 계산하며 모든 경로를 탐색한다.

도착지부터, 목적지까지 오른쪽, 아래, 왼쪽, 위 순서로 DFS

 

 

DFS 전달내용

- 현재 보드 탐색 상황

- 현재 x, y 좌표

- 이전 이동 방향

- 누적 비용

 

#define R 0
#define D 1
#define L 2
#define U 3

// 현재 맵, 현재 x좌표, 현재 y좌표, 이전 진행 방향, 누적 비용 
int dfs(vector<vector<int>> board, int x, int y, int preDir, int p) {

    // 우, 하, 좌, 상 (x, y)
    int dir[2][4] = {{1, 0, -1, 0}, {0, 1, 0, -1}};
    int nowDir[4] = { R, D, L, U };

    for (int i = 0; i < 4; i++) {
        // 진행 방향 설정
        int nowX = x + dir[0][i], nowY = y + dir[1][i];

        if (종료조건) {
            return p;
        }

        if (탐색조건: 탐색지역이 맵을 벗어나지 않는다.) {
            if (탐색조건: 탐색지역은 벽이아니다.) {
                if (커브판별) {
                    dfs(board, nowX, nowY, nowDir[i], p + 100);
                }
                else {
                    dfs(board, nowX, nowY, nowDir[i], p + 600);
                }
            }
        }
    }

 

 

---

비용저장 방법 : 2차원 배열  

DFS를 통한 진행에 따른다.

현 위치 기준 최소 비용 발생 시 해당 경로까지의 비용 저장

 

 

 

입력 [[0,0,0],[0,0,0],[0,0,0]]에 대한  비용 변화

0	1	2	3
0       0       0 0       0       0 0       0       0	0       100     0 0       0       0 0       0       0	0       100     200 0       0       0 0       0       0	0       100     200 0       0       800 0       0       0
4	5	6	7
0       100     200 0       0       800 0       0       900	0       100     200 0       1400    800 0       0       900	0       100     200 0       1400    800 0       2000    900	0       100     200 0       1400    800 2600    2000    900
8	9	10	11
0       100     200 3200    1400    800 2600    2000    900	0       100     200 1500    1400    800 2600    2000    900	0       100     200 1500    1400    800 2100    2000    900	0       100     200 1500    700     800 2100    2000    900
12	13	14	15
0       100     200 1500    700     800 2100    800     900	0       100     200 1500    700     800 1400    800     900	0       100     200 1300    700     800 1400    800     900	0       100     200 100     700     800 1400    800     900
16
0       100     200 100     700     800 200    800     900

 

// 비용저장
int map[36][36];

int dfs(vector<vector<int>> board, int x, int y, int preDir, int p) {

    if (지금 비용이 최저 비용이거나, 비용설정이 되지 않았다) {
        // 비용 갱신
        map[y][x] = p;
    }
}

 

 

 

---

탐색 속도 향상 방법 : 저장된 비용값 비교

현재 탐색할 지역까지의 비용이

누적된 비용보다 비싼경우 탐색 종료

int dfs(vector<vector<int>> board, int x, int y, int preDir, int p) {

    // 비용 설정 조건
    if (지금 비용이 최저 비용이거나, 비용설정이 되지 않았다.) {
        // 비용 갱신
        map[y][x] = p;
    }
    else {
        // 현재 맵에 저장된 비용이 최저 비용이다.
        return map[y][x];
    }
}

 

 

---

최종코드

최종적인 코드다.

#include <iostream>
#include <vector>

using namespace std;

#define R 0
#define D 1
#define L 2
#define U 3

// 비용저장
int map[36][36];

// 현재 맵, 현재 x좌표, 현재 y좌표, 이전 진행 방향, 누적 비용 
int dfs(vector<vector<int>> board, int x, int y, int preDir, int p) {
    // 탐색 완료 표시 : 벽으로 지정
    board[y][x] = 1;

    // 비용 설정 조건 : 지금 비용이 최저 비용이거나, 비용설정이 되지 않았다.
    if (map[y][x] >= p || map[y][x] == 0) {
        // 비용 갱신
        map[y][x] = p;
    }
    else {
        // 현재 맵에 저장된 비용이 최저 비용이다.
        return map[y][x];
    }
    
    // 우, 하, 좌, 상 (x, y)
    int dir[2][4] = {{1, 0, -1, 0}, {0, 1, 0, -1}};
    int nowDir[4] = { R, D, L, U };

    for (int i = 0; i < 4; i++) {
        // 진행 방향 설정
        int nowX = x + dir[0][i], nowY = y + dir[1][i];

        // 종료 조건 : 목적지에 도착했다.
        if (x == y && x == board.size() - 1) {
            return p;
        }

        // 탐색 조건 1 : 탐색지역이 맵을 벗어나지 않는다.
        if ((nowX < board.size() && nowX >= 0) &&
            (nowY < board.size() && nowY >= 0)) {
            // 탐색 조건 2 : 탐색지역은 벽이아니다.
            if (board[nowY][nowX] == 0) {

                // 코너 판정 : 이전과 같은 방향이거나, 시작 지점이다. 
                if (preDir == nowDir[i] || (x == y && x == 0)) {
                    // 건설비용 100
                    dfs(board, nowX, nowY, nowDir[i], p + 100);
                }
                // 이전과 다른 방향이다.
                else {
                    // 건설비용 600(직선 + 코너)
                    dfs(board, nowX, nowY, nowDir[i], p + 600);
                }
            }
        }
    }
}

int solution(vector<vector<int>> board) {

    //탐색 시작
    dfs(board, 0, 0, 0, 0);

    // 도착지에 저장된 최저 비용 반환
    return map[board.size()-1][board.size() - 1];
}