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

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

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

문제 바로가기

자료구조

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

문제 간단 설명

image

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

풀이

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#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;
}

image

회고

  • 너무 어려웠습니다
This post is licensed under CC BY 4.0 by the author.

2021 카카오 채용연계형 인턴십 3번 - 표 편집

정규표현식 사용해보기