728x90
문제
https://www.acmicpc.net/problem/9328
풀이 방법
2차원 공간을 탐색하면서 문서 몇 개를 훔칠 수 있을까를 계산하는 문제다.
이 문제만의 특이한 점은 다음과 같다.
- 처음 시작점이 정해져 있지 않고 주어진 2차원 공간 밖 아무데서나 시작할 수 있다.
- 열쇠를 얻으면 그에 알맞는 문을 열고 지나갈 수 있다. 열쇠는 알파벳 a~z까지 있으므로 총 26개다.
첫 번째는 주어진 2차원 공간 밖의 테두리를 빈 공간으로 만들어준다. 크기를 h+2, w+2로 선언해주는 것이다. 이렇게 하고나서 (0, 0)부터 BFS로 탐색을 시작하면 해결된다.
두 번째는 열쇠를 얻었을 때 문을 제거해주거나, 문을 탐색할 때 열쇠 소지 여부를 판단하고 지나가게 하면 된다. 조심해야 할 것은 공간의 방문 여부가 열쇠를 먹기 전과 먹은 후가 다르다는 것이다.
이를 위해 3차원 visited
배열을 선언해도 되지만 이렇게 하면 열쇠를 0개 먹었을 때 그래프를 모두 탐색하고 1개 먹었을 때 모두 탐색하고 거의 모든 경우를 탐색해보게 될 것이다. 따라서 현재 가진 열쇠 개수보다 더 적은 상태를 탐색하지 않게 추가적인 처리가 필요하다.
반면 아래 코드에서는 단순히 2차원 visited
배열을 선언하고 열쇠를 먹었을 때 방문 여부를 전체 초기화시켜줬다. 그리고 큐에 있는 요소를 모두 제거한 뒤 열쇠를 먹은 자리에서부터 탐색을 하게 만들었다. 또, 열쇠를 먹은 즉시 문을 모두 빈 공간으로 만들어주었다.
코드
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int dy[] = {-1,0,0,1};
int dx[] = {0,-1,1,0};
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int h, w;
bool hasKeys[28] = {false,};
char keys[28] = {0,};
scanf("%d %d", &h, &w);
vector<vector<char>> v(h+2, vector<char>(w+2, '.'));
vector<vector<bool>> visited(h+2, vector<bool>(w+2, false));
for(int i=1; i<=h; i++)
{
for(int j=1; j<=w; j++)
{
char c;
scanf(" %1c", &c);
v[i][j] = c;
}
}
scanf("%s", keys);
for(int i=0; keys[i]!='\0'; i++)
{
hasKeys[keys[i]-'a'] = true;
for(int j=1; j<=h; j++)
{
for(int k=1; k<=w; k++)
{
if(v[j][k]-'A' == keys[i]-'a')
v[j][k] = '.';
}
}
}
int answer = 0;
queue<pair<int, int>> q;
q.push({0,0});
visited[0][0] = true;
while(!q.empty())
{
int y = q.front().first;
int x = q.front().second;
q.pop();
for(int i=0; i<4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || ny >= h+2 || nx < 0 || nx >= w+2)
continue;
if(v[ny][nx] == '*' || visited[ny][nx])
continue;
// 열쇠
if('a' <= v[ny][nx] && v[ny][nx] <= 'z' )
{
// 해당 열쇠를 갖고 있지 않을 경우
if(!hasKeys[v[ny][nx]-'a'])
{
hasKeys[v[ny][nx]-'a'] = true;
// 문 열기
for(int j=1; j<=h; j++)
{
for(int k=1; k<=w; k++)
{
if((v[j][k]-'A') == (v[ny][nx]-'a'))
{
v[j][k] = '.';
}
}
}
// 방문 기록 초기화
fill(visited.begin(), visited.end(), vector<bool>(w+2, false));
while(!q.empty()) q.pop();
}
visited[ny][nx] = true;
q.push({ny,nx});
v[ny][nx] = '.';
}
// 빈 공간
else if(v[ny][nx] == '.')
{
visited[ny][nx] = true;
q.push({ny,nx});
}
// 문서
else if(v[ny][nx] == '$')
{
visited[ny][nx] = true;
q.push({ny,nx});
answer++;
v[ny][nx] = '.';
}
}
}
printf("%d\n", answer);
}
return 0;
}
고찰
혹시 문제 해결에 어려움을 겪고 있다면 아래 글에서 테스트 케이스를 참고해보자.
https://www.acmicpc.net/board/view/69162
728x90