프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
난이도 : Level 3
알고리즘 유형 : 그래프 탐색, BFS, 다익스트라
풀이 시간 : 47분
문제 풀이
자동차 경주에 필요한 경주로를 건설해야 한다. 경주로는 상, 하, 좌, 우 인접한 두 빈 칸을 연결하여 건설할 수 있다.
이때, 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로 라고 하고, 두 직선 도로가 서로 직각으로 만나는 지점을 코너 라고 부른다.
직선 도로 하나를 만들 때는 $100원$이 소요되며, 코너를 하나 만들 때는 $500원$이 추가로 든다. 경주로를 건설하는 데 필요한 최소 비용을 구해보자.
문제의 제한사항을 먼저 살펴보면, 배열의 크기 ≤ $25$ 로 주어졌기 때문에 그래프 탐색을 활용하여 충분히 문제를 풀 수 있을 것으로 생각한다. 하지만, 문제에서 눈여겨봐야할 부분은 최단 거리를 return 하는 것이 아닌, 도로를 건설하는 데 드는 최소 비용을 return하는 것이다.
해당 입출력 예제를 본다면, 파란색 경로는 직선 도로를 10개 짓고, 빨간색 경로는 직선 도로를 12개 짓는다. 하지만, 파란색 경주로는 코너가 5개로 총 $3500원$이 들지만, 빨간색 경주로는 코너가 4개로 총 $3200원$이 들기 때문에, 빨간색 경주로로 짓는 것이 정답이 된다.
이 예제에서 (5, 4) 정점의 경우 중복 방문이 일어나게 되고, 이를 통해 다익스트라 알고리즘을 활용하는 것이 적합함을 알 수 있다.
먼저, visited 배열을 매우 큰 값으로 초기화시켜준다. 이후 visited 배열의 각 원소에는 해당 정점까지 이동하는 데 드는 비용을 저장할 것이다.
만약 해당 정점에 방문했을 때, 현재 정점의 값보다 새로운 방문 비용이 더 많이 든다면 방문하지 못하도록 막는 것이다.
이를 통해 도착 지점까지의 최소 비용을 유지한 채로 지어나갈 수 있다.
하지만, 만약 해당 아이디어까지 생각하게 된다면 다음과 같은 경우에서 문제가 발생한다.
노란색 박스 좌표에서 빨간색과 파란색 경로가 만나게 되는데, 노란색 박스까지 오는 데 걸리는 비용을 계산해본다면 파란색 경로 = $2100원$, 빨간색 경로 = $2300원$이 든다. 하지만 여기서 다익스트라 일고리즘만을 사용하여 문제를 풀어나가게 된다면 문제가 생기게 된다.
만약 빨간색 경로가 노란색 박스에 먼저 도착한 경우라면 문제없이 동작을 하지만, 파란색 경로가 노란색 박스에 먼저 도착한 경우라면 코너에 대해 한 번 더 계산해주기 때문에 도착지에서 최소 비용을 얻지 못하게 된다.(파란색 경로 총 비용 = $3300원$, 빨간색 경로 총 비용 = $3000원$)
따라서 이러한 문제를 방지하기 위해 visited 배열을 2차원이 아닌 경로를 포함한 3차원으로 생성하여 문제를 해결할 수 있다. (`visited[방향][행][열]`)
이 방법을 통해 해당 경로에 서로 다른 방향에서 여러 값이 들어올 수 있고, 이후 발생할 최소 비용을 업데이트 할 수 있게 된다.
해당 방법을 수행하면서 도착지에 여러 값이 도착할 수 있기 때문에, 도착지에 도착하는 모든 경우에 대해 확인해봐야 한다. 하지만, 입력 배열의 크기가 작기 때문에 시간 내에 모든 값을 확인해볼 수 있다.
해당 로직의 시간복잡도로는 $방향 * 행 * 열 = O(4 * N^2)$이 소요된다.
코드
/*
경주로는 상하좌우 이동 가능
두 빈 칸이 같은 방향으로 이동하면 직선도로 : 100원
직각으로 만나는 경우는 코너 : 500원
풀이 : 배열의 크기가 bfs로도 가능해보인다.
bfs에 들어갈 값 : (행, 열, 현재 이동하는 방향)
배열이 중복되어 방문할수도 있기 때문에 다익스트라를 사용하기
*/
#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define INF 999999999
int n;
int visited[4][26][26];
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
void init(vector<vector<int>> &board) {
n = board.size();
for (int d=0;d<4;d++){
for (int i=0;i<n;i++){
for (int j=0;j<n;j++)
visited[d][i][j] = INF;
}
}
}
bool isValid(int r, int c){
return 0 <= r && r < n && 0 <= c && c < n;
}
int dijkstra(int sr, int sc, vector<vector<int>> &board){
queue<pair<int, pair<int, int>>> q;
q.push({-1, {sr, sc}});
for (int i=0;i<4;i++)
visited[i][sr][sc] = 0;
int ans = INF;
while (!q.empty()){
int cur_d = q.front().first; // 이전에 왔던 길의 방향을 저장
int r = q.front().second.first;
int c = q.front().second.second;
q.pop();
for (int d = 0;d < 4; d++){
int nr = r + dr[d], nc = c + dc[d];
if (isValid(nr, nc) && !board[nr][nc]){
int new_cost = 100;
if (cur_d != d)
new_cost += 500;
int total_cost = (cur_d == -1) ? new_cost : visited[cur_d][r][c] + new_cost;
if (visited[d][nr][nc] > total_cost){
// cout << nr << ' ' << nc << ' ' << total_cost << '\n';
if (nr == n - 1 && nc == n - 1){
ans = min(ans, total_cost - 500);
continue;
}
visited[d][nr][nc] = total_cost;
q.push({d, {nr, nc}});
}
}
}
}
return ans;
}
int solution(vector<vector<int>> board) {
init(board);
int answer = dijkstra(0, 0, board);
return answer;
}배운 점
서로 다른 방향에서 온 결과가 최소임을 보장하지 못하는 경우라면 visited 배열을 3차원으로 활용하여 방향 정보도 포함해야 한다는 것에 대해 떠올리는데 꽤 오랜 시간이 소요되었다.
해당 문제는 최소 경로를 찾는 문제가 아닌 그래프 탐색을 활용하면서 여러 경우에 사용된다.
이번 문제를 바탕으로 꼭 까먹지 않고 풀이에 활용해야겠다.