Search
Duplicate
♣️

2021 카카오 채용연계형 인턴십 4번 - 미로 탈출

간단소개
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
알고리즘
태그
Scrap
8 more properties

2021 카카오 채용연계형 인턴십 4번 - 미로 탈출

자료구조

그래프 (인접 리스트)
비트마스크

문제 간단 설명

위 그림에서, Start에서 출발하여 End에 도착하기까지의 최단 거리를 구하면 됩니다.
Trap을 밟게되면, Trap과 인접한 간선들의 방향이 반대가 됩니다.

풀이

1.
함정을 밟을 수 있는 경우의 수를 모두 기록해 놓습니다.
함정의 갯수의 최대값은 10 이므로 상태는 원래 가능한 상태에 2의 10승인 1024배 만큼 늘어나게 됩니다.
원래 노드의 간선의 최대 갯수는 3000개 이므로 4(= sizeof(int)) * 3000이고, 이것에 함정이 추가된 상태인 1024를 곱하면 약 12MB 정도 되므로, 문제를 푸는데에는 무리가 없을 것입니다. (틀릴 수도 있어서.. 피드백 환영합니다)
2.
다익스트라를 적용합니다.
다음 노드가 트랩일 때
트랩을 밟아왔는데, 다음 것이 이미 밟았던 트랩이면
트랩 밟은 것을 없앱니다. 이유는, 밟은 트랩을 또 밟는 것은 안밟은 것이랑 같으므로.
다익스트라 진행
다음 것이 처음 밟는 트랩이면
트랩 밟은걸로 처리합니다.
다익스트라 진행
다음 노드가 트랩이 아닐 때
다익스트라 진행

코드

#include <string> #include <vector> #include <queue> #include <map> #include <cstring> #define MAX 999999999 std::priority_queue<std::pair<int, std::pair<int, int> > > pq;//dist, node, bit std::vector<std::pair<int, int> > g_map[1025][1000]; //node, cost std::map<int, int> trap_map; std::vector<std::vector<int> > g_road; int trap_size; int dist[1025][1001]; bool is_trap(int a) { if(trap_map.find(a) != trap_map.end()) return (1); return (0); } bool trap_check(int a, int bitmask) { if (is_trap(a) && (bitmask & (1 << trap_map[a]))) return (1); return (0); } void combination(int max_depth, int depth, int index, int bitmask) { if (max_depth == depth) { for (auto &i : g_road) { int a = i[0]; int b = i[1]; int cost = i[2]; // 현재 트랩인데 다음 것이 트랩이 아닌 경우, 또는 현재 트랩이 아닌데, 다음 것이 트랩인 경우 if ((trap_check(a, bitmask) && (!trap_check(b, bitmask))) || (!trap_check(a, bitmask)) && (trap_check(b, bitmask))) g_map[bitmask][b].push_back({a, cost}); else g_map[bitmask][a].push_back({b, cost}); } } for (int i = index ; i < trap_size ; i++) { combination(max_depth, depth + 1, i + 1, bitmask | (1 << i) ); } } int solution(int n, int start, int end, std::vector<std::vector<int>> roads, std::vector<int> traps) { int answer = 0; int num = 0; trap_size = traps.size(); std::memset(dist, 0x3f, sizeof(dist)); // 무한대로 초기화 g_road = roads; // trap에 번호 부여. 예를 들면, 첫 번째 트랩이 10이면 {10 : 0} for (auto &i : traps){ trap_map[i] = num++; } //만약 함정을 밟으면, 엣지의 방향이 바뀌므로 미리 다 저장해놓는다. for (int i = 0 ; i <= trap_size ; i++) { combination(i, 0, 0, 0); } pq.push({0, {start, 0}}); while (!pq.empty()){ int distance = -pq.top().first; int node = pq.top().second.first; int bit = pq.top().second.second; pq.pop(); if (dist[bit][node] < distance) continue; for (auto &i : g_map[bit][node]) { int next = i.first; int next_distance = i.second; // 다음것이 트랩일때 if (is_trap(next)) { if (bit & (1 << trap_map[next])) { // 트랩을 밟아왔는데, 다음 꺼가 이미 밟았던 트랩이면 int next_bit = bit ^ (1 << trap_map[next]); if (dist[next_bit][next] < distance + next_distance) // 트랩 밟은걸 없앰 continue; dist[next_bit][next] = distance + next_distance; pq.push({-(distance + next_distance), {next, next_bit}}); } else { int next_bit = bit | 1 << trap_map[next]; if (dist[next_bit][next] < distance + next_distance) continue; dist[next_bit][next] = distance + next_distance; pq.push({-(distance + next_distance), {next, next_bit}}); } } else { if (dist[bit][next] < distance + next_distance) continue; dist[bit][next] = distance + next_distance; pq.push({-(distance + next_distance), {next, bit}}); } } } answer = MAX; for (int i = 0 ; i < 1024 ; i++) if (answer > dist[i][end]) answer = dist[i][end]; return answer; }
C++

회고

너무 어려웠습니다