17244번: 아맞다우산

문제 설명

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

17244번: 아맞다우산

[문제]

 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다.

 "아 맞다 우산!!!"

 경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다.

 외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 종류와 개수가 너무 많았다.

 평소 불필요한 움직임을 아주 싫어하는 경재 씨는 이 물건들을 최대한 빠르게 챙겨서 외출하는 이동 경로를 알고 싶었다.

 경재 씨는 한 걸음에 상하좌우에 인접한 칸으로만 움직일 수 있다.

 경재 씨를 위해 집을 위에서 바라본 모습과 챙겨야 할 물건들의 위치들을 알고 있을 때, 물건을 모두 챙겨서 외출하기까지 최소 몇 걸음이 필요한지 구하는 프로그램을 작성하자.

 

[입력]

 첫 번째 줄에는 집의 가로 길이 N과 세로 길이 M이 입력된다. (3 ≤ N, M ≤ 50)

 두 번째 줄부터는 집의 구조가 예제 입력과 같이 주어진다.

 비어있는 곳은 '.'로 벽은 '#'로 입력된다. 경재 씨의 현재 위치는 S, 나가는 문의 위치는 E, 챙겨야 하는 물건은 종류에 상관없이 X로 입력된다.

 챙겨야 하는 물건은 최대 5개까지 있을 수 있다. 집은 언제나 벽으로 둘러싸여 있고, 나가는 문은 언제나 하나이다.

 

[출력]

 S에서 출발하여 모든 물건을 챙겨서 E까지 도착할 수 있는 최소 시간을 출력한다. 모든 물건을 챙길 수 없는 경우는 주어지지 않는다.

 

[예제 입력 1]

7 6
#######
#SX..X#
#..####
#..X..#
#...X.#
#####E#

[예제 출력 1]

14

---

풀이

 문제의 큰 틀만 보면 기본적인 BFS를 사용한 미로 탐색이지만, 물건을 모두 챙겨야만 나갈 수 있다는 점에서 이를 확인할 상태 변수와 이를 포함하여 중복 방문을 고려할 방문 배열이 필요한 문제이다.

 문제에서 주어진 챙겨할 물건의 최대 개수는 5개이기 때문에, 비트 연산을 활용해도 최대 32 정도로 작은 크기면서 빠른 연산을 활용할 수 있다. 우선 입력을 받을 때 X의 개수를 카운트하여 총 물건 개수를 파악하면서 물건들을 단순 X가 아닌 다른 변수들로 만들고, 정답이 되어야 할 비트를 만들어 놓는다. 추가적으로 시작 위치도 입력을 받을 때 행, 열 변수를 저장을 하고, 이후 BFS를 통한 탐색을 시작한다.

 탐색의 경우에는 크게 별 차이가 없지만, 물건 위치에 있을 때 비트 변수의 변화와 최종 나가는 문일 때 현재 비트 변수가 답안과 동일한 지를 비교하여 이 경우에만 최종 시간을 반환하도록 구현했다.

#include <iostream>
#include <queue>

using namespace std;

char map[50][50];
int xCount, xAnswerBit;
int visited[50][50][1 << 5];

struct infor {
	int r, c, xBit, time;
};

int BFS(int startR, int startC, int N, int M) {
	queue<infor> q;
	q.push({ startR, startC, 0, 0 });

	while (!q.empty()) {
		infor here = q.front(); q.pop();

		//벽 또는 밖이면
		if (map[here.r][here.c] == '#' || 0 > here.r || M <= here.r || 0 > here.c || N <= here.c)
			continue;

		if (map[here.r][here.c] == 'E') //나가는 문이라면
			if (here.xBit == xAnswerBit) //물건 개수도 맞다면
				return here.time;
		
		if (visited[here.r][here.c][here.xBit] == 1) //이미 중복되게 온 곳이면
			continue;

		if ('0' <= map[here.r][here.c] && map[here.r][here.c] < '0' + xCount) { //물건인 경우 처리
			here.xBit |= (1 << (map[here.r][here.c] - '0'));
		}

		visited[here.r][here.c][here.xBit] = 1; //방문 표시
		++here.time;

		++here.c;
		q.push(here);
		--here.c; ++here.r;
		q.push(here);
		--here.r; --here.c;
		q.push(here);
		++here.c; --here.r;
		q.push(here);
	}

	return -1;
}

int main() {
	int N, M;
	int startR = 0, startC = 0;
	string temp;

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		cin >> temp;

		for (int j = 0; j < N; j++) {
			switch (temp[j])
			{
			case 'S':
				startR = i;
				startC = j;
				map[i][j] = temp[j];
				break;
			case 'X':
				map[i][j] = '0' + xCount++;
				break;
			default:
				map[i][j] = temp[j];
				break;
			}
		}
	}

	xAnswerBit = (1 << xCount) - 1;

	cout << BFS(startR, startC, N, M);

	return 0;
}

---

결과