1194번: 달이 차오른다, 가자.

문제 설명

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

1194번: 달이 차오른다, 가자.

[문제]

 지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

 민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

 하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

 영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

 민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

• 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
• 벽 : 절대 이동할 수 없다. (‘#’)
• 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)
• 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)
• 민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
• 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

 달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

 민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

 

[입력]

 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.

 

[출력]

 첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

 

[예제 입력 1]

1 7
f0.F..1

[예제 출력 1]

7

[예제 입력 2]

7 8
a#c#eF.1
.#.#.#..
.#B#D###
0....F.1
C#E#A###
.#.#.#..
d#f#bF.1

[예제 출력 2]

55

---

풀이

 이 문제의 경우 키에 대한 관리와 이 때의 중복 여부 분리가 핵심이었던 문제이다. BFS에서 무한루프를 방지하기 위해 필요한 것이 중복여부(방문여부)에 대한 것인데, 이 문제에선 문을 통과하기 위해 키가 필요하고 키를 얻기 위해 돌아가야 하는 경우도 있다보니 단순히 시간을 기준으로 중복 여부를 계산하면 틀리게 된다.

 그렇기에 특정 위치의 방문 여부를 판별할 때 시간에 키의 상태를 넣어, 특정 위치를 방문했을 때 시간이 늦어도 키를 가지고 있는 상태가 다르다면 탐색을 이어갈 수 있게 하여 이를 해결했다.

 추가적으로 키의 관리는 키의 종류가 최대 6개이기 때문에 모두 다르게 확인을 해줘야하는데, 대표적으로 배열을 사용하거나, 비트마스킹 등으로 관리할 수 있다. 하지만 다르게 생각한 방법이 문자열 상태로 관리하는 것으로, 문과 키 모두 알파벳 순서이기 때문에 이를 이용하여 문자열의 인덱스 접근을 하는 것도 편리하고 큐에 넣는 것도 쉽다 판단하여 이를 적용했다. 

 이로인해 중복 여부를 단순히 배열로 사용할 수 없어, unordered_set<string>을 통해 현재 좌표의 행 + 가진 키의 상태 + 좌표의 열로 문자열을 만들어 중복 여부를 판단했다.

 하지만 결과적으로 시간과 공간 활용을 보았더니 비트마스킹을 사용하는 것이 모든 면에서 이득인거 같다.

#include <iostream>
#include <queue>
#include <unordered_set>
#include <string>

using namespace std;
char map[50][50];
unordered_set<string> visited;//중복 여부

typedef struct infor {//큐에 저장할 정보 구조체
	int r, c, time;
	string getKey;//현재 갖고 있는 키
}infor;

int BFS(int startR, int startC, int N, int M) {
	queue<infor> q;
	q.push({startR, startC, 0, "......" });//시작 위치

	while (!q.empty()) {
		infor now = q.front(); q.pop();
		//인덱스 밖, 벽인 경우
		if (now.r < 0 || N <= now.r || now.c < 0 || M <= now.c || map[now.r][now.c] == '#')
			continue;
		//탈출 지점에 도달한 경우
		if (map[now.r][now.c] == '1')
			return now.time;
		//중복인 경우
		if (visited.find(to_string(now.r) + now.getKey + to_string(now.c)) != visited.end())
			continue;
		//문인 경우(키가 없으면 pass)
		if ('A' <= map[now.r][now.c] && map[now.r][now.c] <= 'F')
			if (now.getKey[map[now.r][now.c] - 'A'] == '.')
				continue;
		//키인 경우
		if ('a' <= map[now.r][now.c] && map[now.r][now.c] <= 'f')
			now.getKey[map[now.r][now.c] - 'a'] = 'o';
		//방문 표시
		visited.insert(to_string(now.r) + now.getKey + to_string(now.c));
		//시간 증가후 상하좌우 큐에 입력
		++now.time;

		++now.r;
		q.push(now);
		--now.r; ++now.c;
		q.push(now);
		now.c -= 2;
		q.push(now);
		++now.c; --now.r;
		q.push(now);
	}

	return -1;
}

int main() {
	int N, M, startR, startC;
	int answer;

	cin >> N >> M;

	for (int i = 0; i < N; i++) {//지도 초기화
		string s;
		cin >> s;
		for (int j = 0; j < M; j++) {
			if (s[j] == '0') {
				startR = i;
				startC = j;
			}
			map[i][j] = s[j];
		}
	}
	
	answer = BFS(startR, startC, N, M);

	cout << answer;

	return 0;
}

---

결과