레벨 4짜리 그래프 문제라 꽤 고생했다... 주말에 그래프 좀 공부하고, 이것저것 시도하면서 박치기했다가 실패하고 해설을 보고 풀었다;
일단 간략하게 해설하자면 위와 같이 노드가 주어진다.
Start 1부터 End 3까지 갈 때 최단거리를 찾는 문제로 흔히 알려진 그래프 다익스트라 문제와 비슷하다.
그러나 이 문제에서 특이한 점은 트랩 노드를 만나면 InOrder를 OutOrder로, OutOrder를 InOrder로 변경해줘야 한다.
예를 들어 노드 1에서 노드 2를 방문하고, 노드 2는 트랩 노드이기때문에 3부터 2로 들어가는 그래프를 2에서 3으로 나가는 그래프로 바꿔줘야 한다.
그 후 2에서 3으로 나가는 그래프를 따라서 노드 3에 Weight 5로 도착하게 된다.
또한 위 사진의 답은 1 -> 2 -> 3 -> 2 -> 4의 순서로 방문하는 4인데, 이처럼 트랩 노드를 여러번 방문할 수도 있다. (즉, 짝수 번째 방문하면 트랩이 꺼진 것이다.)
문제를 다음과 같은 세 가지 단계로 해결했다,
1. Prioriy Queue + Dijkstra (Greedy하게 방문)
2. 그래프를 탐험할 때 지금 어느 트랩노드를 밟고 있는지를 체크하는 상태 값을 관리해줍니다.
3. 현재 노드와 다음 방문 노드 둘 중 트랩이 켜져있는 노드를 체크하여 InOrder, OutOrder 중 어느 엣지를 이용해서 노드를 옮길지를 결정해줍니다.
1. Priority Queue + Dijkstra
Priority Queue + Dijkstra는 기존 Dijstra가 가지는 의 시간복잡도를 로 줄일 수 있는 알고리즘으로, 기존 다익스트라 알고리즘 중 가장 작은 코스트를 가지는 노드를 결정하는 단계를 최적화한 알고리즘이다.
현재 방문 노드에서 방문이 가능한 노드들의 코스트를 구한 뒤 Priority Queue에 Push를 한다면, Priority Queue의 Top 부분이 가장 작은 코스트를 가지는 노드임을 보장할 수 있다.
다익스트라를 진행하는 중 끝나는 지점을 만나면 바로 break를 해도 괜찮은데, 그 이유는 Priority Queue를 이용했고, 시작 노드로부터 모든 지점까지의 최단 거리가 필요없기 때문이다. (Distance 배열을 따로 관리할 필요가 없음)
2. 트랩과 관련된 현재 상태 관리
카카오테크 - 해설과 몇몇 구글링을 통해서 현재 상태를 Bit + XOR로 관리하는 것이 괜찮다고 한다.
위의 사진으로 예를 들어보겠다.
먼저, 트랩 노드가 [2, 3]이면, 2는 인덱스 0번째 트랩노드, 3은 인덱스 1번째 트랩노드라고 설정해준다. (배열으로 관리)
그 후 그래프를 탐험하면서 현재 방문한 노드가 만약 트랩노드라면 몇 번째 트랩노드인지를 알아내고, 해당 인덱스만큼 1을 Left-Shift한 뒤 현재 상태를 XOR해준다. (상태 시작 값은 0이다.)
예를 들어, 2번 노드를 방문할 때에 상태 값은 01이 되고, 그 상태에서 3번 노드를 방문하면 11이 된다. 이 후 다시 2번 노드를 방문하면 10이 되는 것이다.
이로인해 다익스트라에서 중복 방문을 막기 위해 관리하는 visitMap 또한 state별로 관리해줘야 한다.
00 상태에서 2를 방문하였더라도, 11 상태에서 2를 다시 방문 못하면 안되기 때문이다.
3. 다음 노드를 가기 위한 엣지를 결정하는 방법
다음 4개의 케이스가 존재한다.
케이스 1 : 현재 노드가 트랩이 꺼져있고, 다음 노드도 트랩이 꺼져있음
케이스 2 : 현재 노드가 트랩이 꺼져있고, 다음 노드는 트랩이 켜져있음
케이스 3 : 현재 노드가 트랩이 켜져있고, 다음 노드는 트랩이 꺼져있음
케이스 4 : 현재 노드가 트랩이 켜져있고, 다음 노드도 트랩이 켜져있음
먼저 케이스 1, 4의 경우는 기존 그래프를 그대로 이용해도 된다.
그러나 케이스 2, 3의 경우는 InOrder와 OutOrder를 뒤집어서 생각해줘야 한다.
즉, 나가는 엣지는 들어오는 엣지로 생각해주고, 들어오는 엣지는 반대로 나가는 엣지로 생각해줘야 한다.
이를 위해 현재 상태와 현재 노드의 트랩 인덱스를 And 연산 해주고, 현재 상태와 다음 노드의 트랩 인덱스를 And 연산을 해줘서 트랩이 켜진지 여부를 결정했다.
위 사진으로 예를 들어, 현재 상태가 11이라면 3에서 2를 방문할 때 두 노드 모두 트랩이 켜져있는 것이다.
만약 상태가 10이었다면 3에서 2를 방문할 때, 3은 트랩이 켜져있지만 2는 꺼져있는 것이라 InOrder와 OutOrder를 반대로 읽어주면 된다.
정리하자면 다익스트라를 수행하면서 상태를 기록해주고, 현재 방문 노드와 다음 방문 노드의 트랩이 켜져있는지 여부를 체크하여 그래프를 탐색해주면 된다.
코드는 아래와 같다.
#include <string>
#include <vector>
#include <cstdio>
#include <climits>
#include <queue>
#include <cmath>
using namespace std;
typedef struct __node_info {
int cost;
int node;
int state;
}node_info;
int trap_info[1025];
int graph[1001][1001];
int visit[1001][1025];
int answer = INT_MAX;
int trap_size;
// pq는 내림차순으로 정렬해놔야 가장 작은걸 꺼내온다...
struct cmp {
bool operator() (const node_info &a, const node_info &b) {
return a.cost > b.cost;
}
};
void solve(int n, int start, int end)
{
priority_queue<node_info, vector<node_info>, cmp> pq;
pq.push( {0, start, 0} );
while(!pq.empty()) {
node_info cur = pq.top(); pq.pop();
if(cur.node == end) {
answer = cur.cost;
break;
}
int cur_node = cur.node;
int cur_state = cur.state;
int trap_idx = -1;
// 지금 방문하려는 노드가 트랩 노드인지를 체크하고 상태를 변경함
if(trap_info[cur_node]) {
trap_idx = (1 << (trap_info[cur_node] - 1));
cur_state ^= trap_idx;
}
// 이미 현재 상태에서 방문한 적이 있으면 continue (핑퐁될 때, 불필요한 연산 방지)
if(visit[cur_node][cur_state])
continue;
visit[cur_node][cur_state] = 1;
// 새롭게 방문하려는 노드와 현재 노드의 트랩 상태를 체크
// 만약 두 노드의 트랩 on/off 상태가 같다면 정방향 다르다면 역방향으로 cost 체크
for(int i=1;i<=n;i++) {
if(i == cur_node)
continue;
int next_node = i;
bool cur_node_trap_on = false;
bool next_node_trap_on = false;
if(trap_info[cur_node])
if(cur_state & (1 << (trap_info[cur_node] - 1)))
cur_node_trap_on = true;
if(trap_info[next_node])
if(cur_state & (1 << (trap_info[next_node] - 1)))
next_node_trap_on = true;
int from = cur_node_trap_on == next_node_trap_on ? cur_node : i;
int to = cur_node_trap_on == next_node_trap_on ? i : cur_node;
if(graph[from][to] == 0)
continue;
int next_cost = cur.cost + graph[from][to];
node_info next = { next_cost, i, cur_state };
pq.push(next);
}
}
}
int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps)
{
for(auto i : roads)
graph[i[0]][i[1]] = graph[i[0]][i[1]] != 0 ? min(graph[i[0]][i[1]], i[2]) : i [2];
trap_size = traps.size();
for(int i=0;i<trap_size;i++)
trap_info[traps[i]] = i + 1;
solve(n, start, end);
return answer;
}
