경주로 건설

카카오코테 대비 문제를 계속 풀어보았다. 이 문제는 내가 군대 있었을때부터 계속 풀어봤고 풀이 또한 여러번 읽으면서 완전히 익숙한 문제다. 그런데 내 예전 풀이가 테스트케이스가 추가된 순간부터 통과가 안됐었고 군대에 있을때만 해도 도저히 다시 풀어볼 용기가 안났었고 고치는 방법도 몰라서 많이 헤매었던 기억이 난다.

전역을 하고 집에서 문제를 풀면서도 많이 생각했고 결국에 테스트 케이스를 모두 통과할려면 "방향" 의 개념이 필요했다. 동쪽으로 오는 자동차와, 서쪽에서 오는 자동차 모든 케이스를 생각해야 했고 완전탐색에 대한 또다른 생각을 하게 된거같다.

솔직히 시작지점부터 특정지점까지 가는 BFS/DFS 탐색의 문제는 정말 많이 풀었고 2차원 이상의 방문 배열을 사용해서 탐색하는것도 상당히 익숙하다. 그런데 이 문제는 내가 또 다른 생각을 하게 됐는데, 기존에 A 부터 B 지점까지 가는데 필요한 최소 거리 같은 문제 경우 일반적인 BFS 를 사용해서 그 지점까지만 먼저 도착한다면 최소 "거리" 조건을 만족 시켰기 때문에 그대로 반환하면 됐었다.

그러나 이 문제에 경우 특정 지점까지 가기 최소 "비용" 을 묻고 있다. 경로가 아닌 비용이라는 점에서 뭐가 다를까 생각해 봤는데, 경로 같은 경우는 어떤 루트로든 먼저 도착하기만 하면 장땡이다, 하지만 비용 같은 경우는 먼저 도착하는게 장땡이 아닌 좀 더 긴 루트를 돌아서 왔다해도 비용이 더해지는 값이 다르기 때문에 거리가 중요한게 아닌 "어떻게" 오는 경우가 더 중요하다.

일반적인 방문 배열, visited 배열 같은경우는 특정 지점에 이미 방문했다/ 안했다로 쓰이지만 이런 최소 비용 문제에 경우 방문 지점으로 올 수 있는 여러 가지 가능성이 있을때 그 가능성들을 모두 넣어주는게 아니고 방문 지점에 저장되어 있는 비용보다 적을 경우 또 다른 방문을 허용하게 하면 된다.

이 문제를 풀기 위해서 "모든" 경우의 수를 생각해야한다. 가장 먼저 도착점에 오는 경로가 최소 비용이 될 수도 있고, 정말 멀게 돌아오는 지점도 최소 비용이 될 수 있다. 그렇지만 모든 가능성을 visited 안에 저장한다면 당연히 TLE 혹은 Memory 가 터질수도 있다. 그렇기 때문에 일반적으로 visited 배열을 방문 여부인 True/False 로 나누는것보다는 아예 비용을 저장해서 각 지점의 최소 비용을 유지하는게 더 좋은걸 배웠다.

#include <string>
#include <vector>
#include <bits/stdc++.h> 
#define INF 98765432
using namespace std;

struct Car{
    int x,y,dir,cost; 
};

int N; 
int matrix[26][26];
int visited[26][26][4]; 
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}}; //동서남북 
queue<Car> q; 

int solution(vector<vector<int>> board) {
    N = board.size(); 
    int answer = INT_MAX;
    q.push({0,0,-1,0}); 
    memset(visited,INF,sizeof(visited)); 
    while(!q.empty()){
        int size = q.size(); 
        for(int i = 0; i < size; i++){
            Car car = q.front(); 
            q.pop(); 
            int x = car.x, y = car.y, curr_dir = car.dir, curr_cost = car.cost; 
            
            if(x == N-1 && y == N-1){
                answer = min(answer,curr_cost); 
                continue; 
            }
            
            for(int d = 0; d < 4; d++){
                int nX = x + dir[d].first;
                int nY = y + dir[d].second; 
                int nD = d; 
                int nCost = 0; 
                if(nX < 0 || nX >= N || nY < 0 || nY >= N || board[nX][nY] == 1) continue; 
                
                if(curr_dir == -1 || curr_dir == nD) nCost = curr_cost + 100; //직선 도로 
                else nCost =curr_cost + 600; 
                if(visited[nX][nY][nD] > nCost){
                    visited[nX][nY][nD] = nCost; 
                    q.push({nX,nY,nD,nCost}); 
                }
            }
        }
    }
    return answer;
}

배운점:
1. visited 의 또다른 사용법
2. 최소 비용과 최소 경로의 차이점