[프로그래머스/C++] 미로 탈출 (2021 카카오 채용연계형 인턴십)

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 트랩이 있어서 경로가 계속 바뀌는게 특징인 문제다.

만약 트랩이 없다면, 특정 지점에 방문하는 가장 빠른 경로를 구하는 문제와 같기 때문에 최단 경로 알고리즘 중 다익스트라 알고리즘으로 풀 수 있다.

 

처음에는 최단 경로 문제인 것은 알았지만, 트랩 때문에 완전 탐색을 먼저 해보자는 생각이 들었다.

 

여기서 중요한 점은 특정 노드를 방문처리할 때, 트랩이 있기 때문에 한번 방문하면 다시는 방문하지 못하는게 아니라 최대 2번까지 방문이 가능하다는 점이다.

 

여기서 최대 2번까지 방문이 가능한 이유는 트랩을 처음 밟으면 방향이 바뀌는 경우고, 트랩을 그 다음 밟으면 원래 방향으로 바뀌는 경우다. 이후 3번 방문할 경우는 처음 밟는 경우와 같으므로 고려하지 않고, 2번까지만 방문이 가능하다고 고려하고 문제를 풀면 된다.

 

그래서 이를 활용해 DFS로 탐색을 하면서, 트랩을 밟으면 방향을 바꿔주고 몇 번째 방문인지를 기록하도록 코드를 구현했다.

 

여기서 주의해야 할 점은 트랩인 노드는 한 번을 밟는 경우와 두번째 밟는 경우를 비용에 상관없이 모든 경우를 탐색해야한다.

하지만 트랩이 아닌 노드는 경로를 바꾸지 않으므로 비용을 신경써서 가지치기를 할 수 있다.

만약 탐색중에 트랩이 아닌 노드를 처음 방문하는 경우를 생각해보자.

이 때 방문할 경우 비용이 a이고, 트랩을 처음 방문할 때 걸리는 최소 비용이 b로 저장이 되어있다고 가정하면, a와 b를 비교한다.

그리고 이전에 저장된 최소 비용보다 현재 방문할 때 비용이 더 작다면 탐색을 이어가면 된다.

만약 저장된 최소 비용보다 현재 방문할 때 비용이 더 크다면 탐색을 멈추면 된다.

 

이렇게 트랩이 아닌 노드가 가지치기가 가능한 이유는 그림을 보면 이해하기 쉽다. 

음의 간선이 없기 때문에 일반 노드는 최소 횟수를 방문하는게 가장 좋은 방법이다.

그런데 일반 노드를 여러 번 방문하는게 이득인 경우가 이 문제에서는 존재하는데, 이는 트랩을 밟아서 방향을 바꿔야 하는 경우다. 

 

그래서 그림처럼 트랩의 c를 이용하기 위해 일반 노드를 이용하려고 하는데

1. [일반, 트랩, 일반, 트랩]을 거쳐 C를 가는 경로

2. [d경로, 트랩, 일반, 트랩]을 거쳐 C를 가는 경로

의 두 경로가 존재할 수 있다.

 

하지만 잘 보면 1번 경로, 2번 경로 모두 [a, a, b, c], [d, a, b, c]로 왼쪽에 있는 노드를 밟고 트랩 노드를 밟는 경우는 필연적으로 [b, c]를 거쳐서 지나갈 수 밖에 없는 것을 알 수 있다.

 

그렇기 때문에 b, c를 거치기 전인 일반 노드를 한번 밟는 경우는 최솟값을 이용해 가지치기가 가능하다.

 

이 문제에서 가지치기로 탐색의 횟수를 줄이는 부분이 가장 헷갈리기 때문에 그림을 그려보는게 좋다...

 

이렇게 트랩과 일반 노드는 최대 2번만 방문해야 한다는 사실을 파악한다면 DFS로 풀 수 있는 문제였다.

 

+ 다른 사람의 풀이를 보니 다익스트라를 이용해 푼 풀이가 있었다.

트랩을 밟거나 밟지 않은 경우를 1과 0으로 표현해 갈 수 있는 경로들을 on off로 스위칭 해주면서 다익스트라로 문제를 푼 풀이였다.

다익스트라로 푼다면 최소 힙에서 나온 값이 목적지일 경우 값이 최소이므로 바로 return을 해 더 빠르게 문제를 풀 수있다.

 

 

[아이디어 정리]

1. 일반 노드와 트랩 노드는 최대 2번까지 방문이 가능하다.
2. 일반 노드는 처음 밟았을 때, 두번째 밟았을 때 각각 최소 시간을 이용해 가지치기를 할 수 있다.
3. 트랩 노드는 방향이 바뀌기 때문에 가지치기가 불가능하다.
4. DFS로 완전 탐색하며 도착하는데 걸리는 최소 시간를 구했다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <set>
using namespace std;


vector<vector<int>> visited;
vector<int> visitedCnt; // 두번 방문을 위한 처리
set<int> trapSet;
vector<vector<int>>chargeGraph;
vector<set<int>>graphInOut; //
int endN;
void DFS(int nowNode, int charge)
{
    if (nowNode==endN||min(visited[0][endN],visited[1][endN])<=charge)
    {
        return;
    }
    for (set<int>::iterator it=graphInOut[nowNode].begin(); it!=graphInOut[nowNode].end(); it++)
    {
        if (chargeGraph[nowNode][*it]!=9999)// 갈 수 있다면,
        {
            int nowCharge=charge+chargeGraph[nowNode][*it];
            if (trapSet.find(*it)!=trapSet.end()) // 만약 trap이라면,
            {
                if (visitedCnt[*it]<2) // 트랩은 두번까지는 방문이 가능하다. 그 전까지는 무조건 탐색 하는게 맞다.
                {
                    if (visited[visitedCnt[*it]][*it]>nowCharge)
                    {
                        visited[visitedCnt[*it]][*it]=nowCharge;
                        // 방향 바꾸기
                        // *it를 방문햇으므로 *it에서 갈 수 있는 부분들을 전부 바꿔주기
                    }
                    visitedCnt[*it]+=1;
                    int charge1, charge2;
                    for (set<int>::iterator it2=graphInOut[*it].begin(); it2!=graphInOut[*it].end(); it2++)
                    { 
                        charge1 = chargeGraph[*it][*it2];
                        charge2 = chargeGraph[*it2][*it];
                        chargeGraph[*it][*it2]=charge2;
                        chargeGraph[*it2][*it]=charge1;
                    }
                    DFS(*it, nowCharge);
                    for (set<int>::iterator it2=graphInOut[*it].begin(); it2!=graphInOut[*it].end(); it2++)
                    { 
                        charge1 = chargeGraph[*it][*it2];
                        charge2 = chargeGraph[*it2][*it];
                        chargeGraph[*it][*it2]=charge2;
                        chargeGraph[*it2][*it]=charge1;
                    }
                    visitedCnt[*it]-=1;                    
                }
            }
            else
            {
                if (visitedCnt[*it]<2)
                {
                    if (visited[visitedCnt[*it]][*it]>nowCharge) //가지치기
                    {
                        visited[visitedCnt[*it]][*it]=nowCharge;
                        visitedCnt[*it]+=1;
                        DFS(*it, nowCharge);
                        visitedCnt[*it]-=1;
                    }
                }
            }
        }
    }
}


int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    int answer = 0;
    endN=end;
    visited=vector<vector<int>>(2,vector<int>(n+1,6000001));
    visitedCnt=vector<int> (n+1,0);
    trapSet=set<int>(traps.begin(), traps.end());
    chargeGraph=vector<vector<int>>(n+1, vector<int>(n+1,9999));
    graphInOut=vector<set<int>>(n+1); //
    for (int i=0; i<roads.size(); i++)
    {
        if (chargeGraph[roads[i][0]][roads[i][1]]>roads[i][2])
        {
            chargeGraph[roads[i][0]][roads[i][1]]=roads[i][2];
        }        
        graphInOut[roads[i][0]].insert(roads[i][1]);
        graphInOut[roads[i][1]].insert(roads[i][0]);
    }
    DFS(start, 0);    

    return min(visited[0][end],visited[1][end]);
}

 

---

다익스트라가 바로 떠올랐다면, 문제풀이가 좀 달라졌을 것 같은데 바로 떠오르지 않아서 가지치기와 DFS로 풀었다...

처음 문제를 봤을 때 쉬울것 같다고 생각했지만, 생각보다 어려운 문제였다.

 

프로그래머스