[백준] 9328번: 열쇠 (c++)

 

문제

---

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

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

9328번: 열쇠

 

문제조건

---

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

• '.'는 빈 공간을 나타낸다.
• '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
• '$'는 상근이가 훔쳐야하는 문서이다.
• 알파벳 대문자는 문을 나타낸다.
• 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

 

풀이

---

BFS를 사용하는 문제. 하지만 그냥 BFS를 하면 시간 초과가 난다.

조건에 의하면 가장자리 값들로만 빌딩으로 들어갈 수 있다. for문을 가장자리 값들을 돌며 확인 할 수 있지만 너무 복잡하다. 이렇게 가장자리 값들로만 들어갈 수 있을때는 밖에 1줄의 빈 칸들을 덧붙여서 평소 BFS를 풀듯이 [0,0] 좌표부터 살펴보면 보다 간단하게 문제를 풀 수 있다.

열쇠를 여러번 사용할 수 있으므로 열쇠를 찾을 때마다 열 수 있는 문들을 미리 다 열어 놓았다(.로 값 변경). 상하좌우로 움직이며 각 값들을 확인해보면 정답을 찾을 수 있다. 하지만 그냥 BFS를 하다보면 시간 초과가 난다. BFS를 너무 많이하기 때문이다. 이를 해결하기 위해서 queue를 사용하여 이전 방문 값들을 저장하고 조건을 만족하지 않으면 continue하는 식으로 진행해 주었다. 

어렵다... 아래 시간초과가 나는 코드는 100*100짜리 맵을 통과하지 못하는걸 보면 틀린 코드인 것 같다.

 

코드

---

시간 초과

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include<cstring>

using namespace std;
char docMap[102][102];
bool visited[102][102];
bool alphaKeys[26];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0,0,1,-1 };
int H, W;
int ans = 0;
// .:empty, *: wall, $: document

void init() {
	memset(alphaKeys, false, sizeof(alphaKeys));
	for (int i = 0; i < 102; i++) {
		memset(docMap[i], '.', sizeof(docMap[i]));
		memset(visited[i], false, sizeof(visited[i]));
	}
}

void openDoor(char c) {
	for (int j = 1; j <= H; j++) {
		for (int k = 1; k <= W; k++) {
			if (docMap[j][k] == 'A' + c - 'a') docMap[j][k] = '.';
		}
	}
}

void find(int y, int x) {
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= 0 && ny <= H+1 && nx >= 0 && nx <= W+1 && !visited[ny][nx]) {
			char newSpace = docMap[ny][nx];
			if (newSpace == '*') continue;
			//문서 발견!
			if (newSpace == '$') {
				//중복 방지를 위해 .로 바꾸기
				docMap[ny][nx] = '.'; 
				ans++;
				visited[ny][nx] = true;
				find(ny, nx);
				visited[ny][nx] = false;
			}

			//비어있을때
			if (newSpace == '.') {
				visited[ny][nx]=true;
				find(ny, nx);
				visited[ny][nx] = false;
			}

			//소문자일때
			if (newSpace >= 'a' && newSpace <= 'z') {
				alphaKeys[newSpace - 'a'] = true;
				docMap[ny][nx] = '.';
				visited[ny][nx]=true;
				openDoor(newSpace);
				// 키가 새로 열렸음으로 처음부터 다시 시작해야함
				visited[ny][nx] = true;
				find(ny, nx);
				visited[ny][nx] = false;
			}

			//대문자일때 -> 키가 있었다면 이미 .로 열려 있음
		}
		
	}
}

int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> H >> W;
		init();
		for (int j = 1; j <= H; j++) {
			for (int k = 1; k <= W; k++) {
				cin >> docMap[j][k];
			}
		}

		string s;
		cin >> s;
		if (s[0] != '0') {
			for (int j = 0; j < s.length(); j++) {
				alphaKeys[s[j] - 'a'] = true;
				openDoor(s[j]);
			}
		}
		
		find(0,0);
		
		cout << ans << "\n";
		ans = 0;
	}
}

 

맞은 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include<cstring>

using namespace std;
char docMap[102][102];
bool visited[102][102];
bool alphaKeys[26];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0,0,1,-1 };
int H, W;
int ans = 0;
// .:empty, *: wall, $: document

void init() {
	memset(alphaKeys, false, sizeof(alphaKeys));
	for (int i = 0; i <= 101; i++) {
		memset(docMap[i], '.', sizeof(docMap[i]));
		memset(visited[i], false, sizeof(visited[i]));
	}
}

void openDoor(char c) {
	for (int j = 1; j <= H; j++) {
		for (int k = 1; k <= W; k++) {
			if (docMap[j][k] == 'A' + c - 'a') docMap[j][k] = '.';
		}
	}
}

void find(int y, int x) {
    queue<pair<int, int>> q;

    q.push(make_pair(y, x));



    while (!q.empty())

    {
        int curY = q.front().first;
        int curX = q.front().second;
        q.pop();


        //범위 확인
        if (curY < 0 || curY > H + 1 || curX < 0 || curX > W + 1)
            continue;

        //이미 방문한 지점이거나, 벽이거나, 잠긴 문
        if (visited[curY][curX] || docMap[curY][curX] == '*' || ('A' <= docMap[curY][curX] && docMap[curY][curX] <= 'Z'))
            continue;

        visited[curY][curX] = true;

        //문서
        if (docMap[curY][curX] == '$')
        {
            ans++;
            docMap[curY][curX] = '.';
        }

        //열쇠

        if ('a' <= docMap[curY][curX] && docMap[curY][curX] <= 'z')
        {
            char key = docMap[curY][curX];
            docMap[curY][curX] = '.';

            if (alphaKeys[key-'a'] == false)
            {
                alphaKeys[key - 'a'] = true;
                openDoor(key);

                //모든 경로를 다시 확인
                memset(visited, false, sizeof(visited));
                while (!q.empty())
                    q.pop();
                q.push(make_pair(curY, curX));
                continue;
            }
        }

        // 이동
        for (int i = 0; i < 4; i++)
        {
            int ny = curY + dy[i];
            int nx = curX + dx[i];
            q.push(make_pair(ny, nx));
        }

    }
}

int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> H >> W;
		init();
		for (int j = 1; j <= H; j++) {
			for (int k = 1; k <= W; k++) {
				cin >> docMap[j][k];
			}
		}

		string s;
		cin >> s;
		if (s[0] != '0') {
			for (int j = 0; j < s.length(); j++) {
				alphaKeys[s[j] - 'a'] = true;
				openDoor(s[j]);
			}
		}
		
		find(0,0);
		
		cout << ans << "\n";
		ans = 0;
	}
}