[C++/백준] 17244. 아맞다우산

문제

https://www.acmicpc.net/problem/17244

17244번: 아맞다우산

2차원 맵에서, 출발에서 도착점으로 가는데, X로 표시된 필요한 물건들을 모두 챙겨서 나가는 최소 이동거리를 구하는 문제이다. 

 

풀이

그래프상에서 최소 이동 횟수를 구하는 문제이기 때문에 BFS를 이용했다. 

그리고, 그래프상에 X가 있는 지점을 모두 방문하는게 조건이기 때문에 X방문체크를 어떻게 할지 고민하다가, X가 최대 5개라고 해서 길이 5짜리 비트마스크를 이용해서 방문체크를 해주었다. 

 

각 X들을 구분하기 위해, 입력받을 때 X를 각기 다른 숫자(0~5)로 바꿔주었다. 

 

코드

#include <iostream>
#include <queue>

#define sc scanf_s

using namespace std;

int N, M;
char table[51][51];
bool visited[51][51][1 << 5];
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int x = 0; //X개수

struct Node {
	int r; int c; int bitmap; int count;
};
int BFS(int startR, int startC) {
	queue<Node> q;
	q.push({ startR, startC, 0, 0 });

	while (!q.empty()) {
		int r = q.front().r;
		int c = q.front().c;
		int bitmap = q.front().bitmap;
		int count = q.front().count;
		q.pop();
		for (int i = 0;i < 4;i++) {
			int newR = r + dr[i]; int newC = c + dc[i];
			if (newR < 0 || newR >= M || newC < 0 || newC >= N) continue;
			if (table[newR][newC] == '#') continue;
			else if (table[newR][newC] == 'E') {
				if (bitmap == (1 << x)-1) {
					return count + 1;
				}
				if (!visited[newR][newC][bitmap]) {
					q.push({ newR, newC, bitmap, count + 1 });
					visited[newR][newC][bitmap] = 1;
				}
			}
			else if (table[newR][newC] == '.') { // 평범
				if (!visited[newR][newC][bitmap]) {
					q.push({ newR, newC, bitmap, count + 1 });
					visited[newR][newC][bitmap] = 1;
				}
					
			} 
			else { // X
				int temp = table[newR][newC] - '0';
				int newBitmap = bitmap | (1 << temp);
				if (!visited[newR][newC][newBitmap]) {
					q.push({ newR,newC,newBitmap,count + 1 });
					visited[newR][newC][newBitmap] = 1;
				}
			}
		}
	}
	return -1;
}
int main() {
	sc("%d %d", &N, &M); // N : col, M : row
	int startR, startC;
	for (int m = 0;m < M;m++) {
		for (int n = 0;n < N;n++) {
			sc("%c", &table[m][n]); // %c 앞에 공백 넣어주기 별표다섯개
			if (table[m][n] == 'X') {
				//table[m][n] = x + '0';
				x++;
			}
			else if (table[m][n] == 'S') {
				startR = m;
				startC = n;
				table[m][n] = '.';
			}
		}
	}
	int result = BFS(startR, startC);
	printf("%d\n", result);
	return 0;
}

 

결과