문제 이해 단계
https://www.acmicpc.net/problem/9328
9328번: 열쇠
상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가
www.acmicpc.net
높이 h와 너비 w를 가진 2차원 맵이 존재한다.
여기서 원하는 것은 문서를 최대한 많이 획득하는 것이다.
'. ' : 빈 공간
' * ' : 벽
' $ ' : 문서
알파벳 대문자 : 잠겨 있는 문
알파벳 소문자 : 열쇠 해당 문자의 대문자에 해당하는 문을 열 수 있음
처음에는 빌딩 밖에 있고, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다.
그리고 같은 열쇠를 여러 번 사용할 수 있다.
이러한 조건일 때 획득할 수 있는 문서의 최대 개수를 구하는 문제
문제 접근 단계
지도의 높이와 너비는 최대 100x100까지 가능하다.
그리고 열쇠는 모두 알파벳으로만 이뤄져 있기 때문에 최대 26개까지다.
일단 제한사항이 맵이 너무 크거나, 열쇠가 많지는 않다.
그래서 시간초과나 자료형을 신경 쓸 필요 없어 보인다.
일반적인 그래프 탐색 기법이 힘든 이유
여기서 문제가 되는 부분은 열쇠와 문의 종류가 다 다르다는 것이다.
그리고 일반적인 그래프 탐색으로 풀기엔 무리가 있다.
여기서는 상하좌우로 움직이기 때문에 BFS 혹은 DFS를 사용해야 하는데,
둘 다 탐색했던 지점은 다시 가지 않기 때문에 뒤늦게 열쇠를 획득했을 때가 문제가 된다.
예를 들어, 아래 그림에서 아무런 열쇠를 가지지 않고 출발했다고 가정해 보자.
초록색 경로로 갈 때, 문 A를 검사하면 당연히 아무런 열쇠가 없기 때문에 통과하지 못한다.
그리고 벽에 막힌 것과 똑같기 때문에
다른 방향으로 가기 위해 방문처리를 하고 돌아온다.
이후 BFS든 DFS든 절차에 의해 열쇠 a를 먹는다.
열쇠 a를 얻어도 이미 문 A의 경로는 방문을 했으므로 더 이상 갈 수 없다.
그래서 일반적인 BFS나 DFS는 할 수 없다.
해결법
이 문제를 어떻게 해결하면 좋을까?
만약 문 A를 탐색할 때 열쇠 a가 있어서 그대로 지나갔다고 가정해 보자.
그럼 당연히 문 A 좌표로 이동한 뒤,
그 좌표에서 상하좌우로 이동하는 것을 반복할 것이다.
이 행동을 열쇠 a를 얻을 때까지 잠시 멈췄다고 생각하는 것이다.
즉, 열쇠가 없는 상태에서 문을 만나면 그 문의 좌표를 저장해 둔다.
그리고 그 열쇠를 획득하면 바로 그 좌표로 워프 하여 그 위치부터 다시 그래프 탐색을 하는 것이다.
그래프 탐색하는 방법으로 BFS를 사용할 것이고,
문도 여러 개가 있어 좌표가 여러 개가 나올 수 있으므로 문의 좌표를 저장해 두는 26개의 큐를 더 만든다.
이는 A~Z까지의 문에 해당하는 큐다.
만약 문에 해당하는 열쇠를 얻으면 해당 큐 안에 들어있는 모든 원소들을 BFS를 하는 큐에 옮긴다.
이러한 방식으로 워프를 구현한다.
이 외에는 일반적인 BFS와 같다.
출발 지점 정하기
문과 열쇠를 찾아서 경로를 이동하는 방법 다 알겠다.
근데 출발 지점을 어디로 정해야 하는 걸까?
"빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다."
해당 문제에서 제시한 조건이다.
처음에는 왼쪽으로 들어갔다가 그다음 오른쪽으로 들어갈 수도 있다는 소리이다.
여기서 또 한 가지 유의해야 할 점은
'. '으로만 들어갈 수 있는 것이 아니라,
'$'이나 열쇠 심지어는 문으로도 들어갈 수 있다는 점이다.
특히 문으로 들어갈 때를 주의해야 한다.
처음에는 열쇠가 없어서 문으로 들어가지 못했던 외곽이
나중에는 열쇠를 획득해서 들어갈 수 있는 입구가 될 수도 있기 때문이다.
이 모든 걸 예외 처리하고, 일일이 체크하기에는 머리 아프다.
그래서 문제에서 말하는 것처럼 빌딩 외곽을 돌 수 있도록 맵에 가상의 외곽을 하나 더 만든다.
파란색이 입력으로 주어진 맵의 크기이고, 노란색으로 된 것이 가상으로 만든 외곽이다.
위 방법을 사용하면 모든 외곽을 돌면서 체크할 수 있다.
이제 위의 방법을 모두 합쳐서 문제 구현 단계에서 코드로 설명하겠다.
문제 구현 단계
#define X first
#define Y second
int dx[] = {1,-1,0,0};
int dy[] = {0,0,-1,1};
char maps[102][102];
bool visited[102][102] = {false,};
unordered_set<char> key; // 현재 가지고 있는 키
int h,w;
int ans = 0; // 문서 개수
// bfs 탐색
void search(int sx, int sy){
queue<pair<int,int>> q; // Bfs 큐
queue<pair<int,int>> door[27]; // 각 알파벳 문의 큐
visited[sx][sy] = true;
q.push({sx,sy});
while(!q.empty()){
int x = q.front().X;
int y = q.front().Y;
q.pop();
// 현재 있는 곳이 $ 이면 정답 개수 +1
if(maps[x][y] == '$') ans++;
// 상하좌우 움직임
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
char ch = maps[nx][ny]; // 다음 위치의 단어
// 이미 방문했거나, 벽이거나, 범위 밖으로 벗어나면 안됨
if(nx < 0 || ny < 0 || nx > h+1 || ny > w+1||
visited[nx][ny] || ch == '*') continue;
visited[nx][ny] = true;
// 다음 위치가 문이라면
if('A' <= ch && ch <= 'Z'){
// 현재 해당 문의 키를 가지고 있지 않으면 해당 문의 큐에 넣음
if(key.count(ch+32) == 0) door[ch-'A'].push({nx,ny});
// 해당 문의 키를 가지고 있으면 bfs 큐에 넣음
else q.push({nx,ny});
}
// 다음 위치가 열쇠
else if('a'<= ch && ch <= 'z'){
key.insert(ch); // 열쇠 개수 추가
int idx = ch-'a'; // 해당 열쇠에 대응하는 문의 알파벳 인덱스
// 해당 문의 큐 안에 있는걸 전부 bfs 큐로 옮김
while(!door[idx].empty()){
q.push(door[idx].front());
door[idx].pop();
}
q.push({nx,ny}); // 열쇠 칸으로 이동한 것을 큐에 넣음
}
// 다음 위치가 . 또는 $ 일때
else q.push({nx,ny});
}
}
}핵심적인 코드 부분이다.
우선 전역변수부터 설명하자면, unordered_set으로 만든 key로 현재 가지고 있는 열쇠를 저장한다.
그리고 ans에 도달한 문서의 개수를 저장한다.
search 함수를 보면 , bfs를 진행하는 큐와, 알파벳 문의 큐가 존재한다.
이후로는 상하좌우로 탐색하는 것을 진행하는데,
문을 만나면 해당 문에 대응하는 키가 key set에 있는지 확인한다.
만약 있다면 bfs큐에 넣고 진행하고, 없다면 해당 문에 해당하는 큐에 넣는다.
여기서 key.count(ch+32)에서 32를 더해주는 이유는
아스키코드에서 대문자에서 32를 더해주면 소문자가 되기 때문이다.
탐색을 하다가 열쇠를 만나면, 해당 열쇠를 key set에 추가한다.
그리고 해당 열쇠에 대응하는 문의 큐에 위치가 저장되어 있을 수도 있기 때문에 이를 모두 bfs로 옮긴다.
즉 워프 한다고 보면 된다.
그리고 열쇠 칸으로 이동한다.
' . '이나 $를 만난다면 그냥 일반적인 BFS처럼 진행해 준다.
여기까지가 핵심적인 함수에 대한 설명의 끝이다.
이제 전체 코드를 올리고 포스팅을 마치겠다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <unordered_set>
using namespace std;
#define X first
#define Y second
int dx[] = {1,-1,0,0};
int dy[] = {0,0,-1,1};
char maps[102][102];
bool visited[102][102] = {false,};
unordered_set<char> key; // 현재 가지고 있는 키
int h,w;
int ans = 0; // 문서 개수
// bfs 탐색
void search(int sx, int sy){
queue<pair<int,int>> q; // Bfs 큐
queue<pair<int,int>> door[27]; // 각 알파벳 문의 큐
visited[sx][sy] = true;
q.push({sx,sy});
while(!q.empty()){
int x = q.front().X;
int y = q.front().Y;
q.pop();
// 현재 있는 곳이 $ 이면 정답 개수 +1
if(maps[x][y] == '$') ans++;
// 상하좌우 움직임
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
char ch = maps[nx][ny]; // 다음 위치의 단어
// 이미 방문했거나, 벽이거나, 범위 밖으로 벗어나면 안됨
if(nx < 0 || ny < 0 || nx > h+1 || ny > w+1||
visited[nx][ny] || ch == '*') continue;
visited[nx][ny] = true;
// 다음 위치가 문이라면
if('A' <= ch && ch <= 'Z'){
// 현재 해당 문의 키를 가지고 있지 않으면 해당 문의 큐에 넣음
if(key.count(ch+32) == 0) door[ch-'A'].push({nx,ny});
// 해당 문의 키를 가지고 있으면 bfs 큐에 넣음
else q.push({nx,ny});
}
// 다음 위치가 열쇠
else if('a'<= ch && ch <= 'z'){
key.insert(ch); // 열쇠 개수 추가
int idx = ch-'a'; // 해당 열쇠에 대응하는 문의 알파벳 인덱스
// 해당 문의 큐 안에 있는걸 전부 bfs 큐로 옮김
while(!door[idx].empty()){
q.push(door[idx].front());
door[idx].pop();
}
q.push({nx,ny}); // 열쇠 칸으로 이동한 것을 큐에 넣음
}
// 다음 위치가 . 또는 $ 일때
else q.push({nx,ny});
}
}
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T;
cin >> T;
while(T--){
ans = 0;
fill(&maps[0][0],&maps[100][101],' ');
fill(&visited[0][0],&visited[100][101],false);
key.clear();
vector<pair<int,int>> start;
cin >> h >> w;
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
cin >> maps[i][j];
if(((i == 1 || i == h) && (1 <= j && j <= w))
|| ((1 <= i && i <= h) && (j == 1 || j == w)))
{
if('a' <= maps[i][j] && maps[i][j] <= 'z') {
key.insert(maps[i][j]);
start.push_back({i,j});
}
if(maps[i][j] == '.' || maps[i][j] == '$') start.push_back({i,j});
}
}
}
string has;
cin >> has;
for(auto it : has) key.insert(it);
search(0,0);
cout << ans << "\n";
}
}시행착오
처음에는 열쇠에서부터 시작하여 외곽에 닿으면 성공하는 방식으로 했는데, 완전히 잘못짚었다.
문제를 스스로 더 어렵게 만들어버렸다.
이 문제에 한 5시간 쓴 것 같은데 완전히 헛다리 짚은 것 같아서 짜증 난다.
인터넷을 참고해서 풀이를 보는데, 너무 직관적이고 간결해서 초라해진다.
처음에는 DFS + DP 문제인 줄 알았는데 그냥 BFS 문제였다.
큐를 여러 개를 사용해서 문제를 풀다니 신박했다.
생활비..