[Programmers] 미로 탈출

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/81304

프로그래머스

 
함정의 개수가 최대 10개이므로 비트마스킹과 다익스트라 알고리즘을 사용하는 문제였습니다.
 
알고리즘은 다음과 같습니다.
1. 주어진 파라미터를 토대로 전처리를 진행합니다.

• traps에 포함된 방 번호에 대해 각 방을 bitmask의 몇 번째 비트에 매핑할지 결정 (trap2idx)
• 원래 방향의 edge (u -> v)는 현재 상태에서 u의 활성 여부와 v의 활성 여부가 같은 때 (즉, XOR가 false) 유효하며 역방향의 edge (v → u)는 현재 상태에서 u와 v의 활성 여부가 다를 때 (즉, XOR가 true) 유효
  • 두 케이스 모두 고려해야하므로 인접그래프를 정방향, 역방향 모두 구성 (graph, reverseGraph)

 
2. 다익스트라 알고리즘을 아래 로직과 함께 진행합니다.

• 상태 (curNode, mask)에 대해, 현재방의 함정 활성 여부(curActivated)를 확인
• 정방향 edge (graph[curNode]): 다음 방의 함정 활성 여부(nextActivated)가 현재방과 같다면 edge가 유효
• 역방향 edge (reverseGraph[curNode]): 다음 방의 함정 활성 여부가 현재방과 다르다면 edge가 유효
• 도착한 방이 함정이면 mask를 토글
• 목적지(end)에 도달하는 상태가 나오면 바로 그 비용을 반환

 

	#include <string>
	#include <vector>
	#include <queue>
	#include <limits>
	using namespace std;
	const long long INF = 1e18;
	const int MAX = 1e3 + 1;
	// 상태 구조체 : cost(누적 이동시간), node(현재 방), mask(함정 상태 bitmask)
	typedef struct
	{
	long long cost;
	int node;
	int mask;
	} State;
	bool operator<(State a, State b)
	{
	return a.cost > b.cost;
	}
	vector<pair<int, int>> graph[MAX];
	vector<pair<int, int>> reverseGraph[MAX];
	int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
	// traps에 포함된 방 번호에 대해 각 방을 bitmask의 몇 번째 비트에 매핑할지 결정
	int trapCnt = traps.size();
	vector<int> trap2idx(n + 1, -1);
	for (int i = 0; i < trapCnt; i++)
	{
	trap2idx[traps[i]] = i;
	}
	for (auto road : roads)
	{
	int u = road[0];
	int v = road[1];
	int w = road[2];
	graph[u].push_back({v, w});
	reverseGraph[v].push_back({u, w});
	}
	// dist[node][mask] : 현재 방 'node'에 trap상태 'mask'로 도착했을 때 최소 이동시간
	vector<vector<long long>> dist(n + 1, vector<long long>(1 << trapCnt, INF));
	dist[start][0] = 0;
	priority_queue<State> pq;
	pq.push({0, start, 0});
	while (!pq.empty())
	{
	State curState = pq.top();
	pq.pop();
	long long curCost = curState.cost;
	int curNode = curState.node;
	int mask = curState.mask;
	// 도착 방에 도달하면, 현재까지의 최소 비용이 답
	if (curNode == end)
	{
	return curCost;
	}
	if (curCost > dist[curNode][mask])
	{
	continue;
	}
	// 현재 방(curNode)이 함정이라면 현재 mask에서 활성여부를 확인
	bool curActivated = false;
	if (trap2idx[curNode] != -1)
	{
	if (mask & (1 << trap2idx[curNode]))
	{
	curActivated = true;
	}
	}
	// 원래 curNode에서 나가는 edge (graph[curNode]) 확인
	// 원래 edge (cur->next)는, 현재 상태에서 cur와 nxt의 활성 여부가 같을 때 유효
	for (auto edge : graph[curNode])
	{
	int next = edge.first;
	int w = edge.second;
	bool nextActivated = false;
	if (trap2idx[next] != -1)
	{
	if (mask & (1 << trap2idx[next]))
	{
	nextActivated = true;
	}
	}
	if (curActivated == nextActivated)
	{
	int nextMask = mask;
	// 도착 방이 함정이면, 상태 토글
	if (trap2idx[next] != -1)
	{
	nextMask = mask ^ (1 << trap2idx[next]);
	}
	if (dist[next][nextMask] > curCost + w)
	{
	dist[next][nextMask] = curCost + w;
	pq.push({curCost + w, next, nextMask});
	}
	}
	}
	// 원래 다른 노드에서 curNode로 들어오는 edge (reverseGraph[curNode]) 확인
	// 이 경우, 원래 edge는 (next -> cur)이지만, 현재 상태에서 방향이 뒤집혀 cur->next로
	// 갈 수 있으려면 cur와 next의 활성 여부가 달라야 함
	for (auto edge : reverseGraph[curNode])
	{
	int next = edge.first;
	int w = edge.second;
	bool nextActivated = false;
	if (trap2idx[next] != -1)
	{
	if (mask & (1 << trap2idx[next]))
	{
	nextActivated = true;
	}
	}
	if (curActivated != nextActivated)
	{
	int nextMask = mask;
	if (trap2idx[next] != -1)
	{
	nextMask = mask ^ (1 << trap2idx[next]);
	}
	if (dist[next][nextMask] > curCost + w)
	{
	dist[next][nextMask] = curCost + w;
	pq.push({curCost + w, next, nextMask});
	}
	}
	}
	}
	return -1;
	}

view raw .cpp hosted with ❤ by GitHub

 
 
개발환경: Programmers IDE  
 
지적, 조언, 질문 환영합니다! 질문 남겨주세요~