[프로그래머스/C++] 경주로 건설 (2020 카카오 인턴십)

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 최소 비용을 구하는 탐색 문제다.

 

길을 연결하기 위해 드는 비용이 음의 값을 갖지 않고 시작위치와 끝 위치가 정해져있기 때문에 쉽게 풀 수 있는 문제다.

 

나는 BFS와 memoization을 이용해 풀기로 했다.

 

코너를 만들 때 비용이 추가가 되므로, 이를 구분하기 위해 방향을 구분할 필요가 있다.

 

그래서 내가 세로 방향으로 이동중이였는지 가로방향으로 이동중이였는지를 구분하고, 만약 가로 방향에서 세로로 방향을 바꾸거나 세로에서 가로로 방향을 바꾸면 비용을 추가해 비교하도록 코드를 구현했다.

 

그리고 이전에 y, x 지점을 세로방향으로 방문했을 경우 이번에 방문한 경우의 비용이 더 적다면 다시 탐색을 하도록 했다. 

만약 이번에 방문한 비용이 더 많이 들었다면, 이전에 방문한 경로가 더 좋은 경로이므로 더 이상 탐색을 하지 않도록 했다.

 

​

[아이디어 정리]

1. memoization을 이용해 특정 지점에 도달하는 비용을 비교해 queue에 삽입할지 말지를 정한다.
2. 코너의 경우 비용이 추가가 되기 때문에 방향의 구분이 필요하므로, 세로와 가로 방향으로 구분한다.
3. 최종적으로 도달했을 때 비용중 최소값을 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <queue>
using namespace std;
int dy[4]={1,0,-1,0}; //세로 방향이동
int dx[4]={0,1,0,-1};

void BFS(vector<vector<int>> &board, vector<vector<vector<int>>> &costBoard)
{
    vector<int> nowV(4,0); //y, x, cost, dir => 0세로, 1가로
    queue<vector<int>> Q;
    int ny, nx, nc,bSize=board.size();
    Q.push(nowV), costBoard[0][0][0]=0,costBoard[0][0][1]=0;
    nowV[3]=1;
    Q.push(nowV);
    while(!Q.empty())
    {
        nowV=Q.front();
        Q.pop();
        if (nowV[2]==costBoard[nowV[0]][nowV[1]][nowV[3]])
        {
            for (int i=0; i<4; i++) //세로이동
            {
                int idx=i%2;
                ny=nowV[0]+dy[i];
                nx=nowV[1]+dx[i];
                if (0<=ny&&ny<bSize&&0<=nx&&nx<bSize&&board[ny][nx]!=1)
                {
                    if (nowV[3]==idx) //i%2가 0이면 세로 방향이동할 차례
                    {
                        nc=nowV[2]+1;
                    }
                    else
                    {
                        nc=nowV[2]+6;
                    }
                    if (costBoard[ny][nx][idx]>nc)
                    {
                        costBoard[ny][nx][idx]=nc;
                        Q.push({ny,nx,nc,idx});
                    }                    
                }
            }
        }        
    }
}

int solution(vector<vector<int>> board) {
    int answer = 0;
    vector<vector<vector<int>>> costBoard(board.size(),vector<vector<int>>(board[0].size(),vector<int>(2,100000))); 
    BFS(board,costBoard);
    return min(costBoard[board.size()-1][board.size()-1][0],costBoard[board.size()-1][board.size()-1][1])*100;
}

 

---

 

가로와 세로 방향을 구분만 하면 어렵지 않은 문제라 쉽게 풀었다.

 

 

프로그래머스