백준 9328번 열쇠

문제 링크입니다: https://www.acmicpc.net/problem/9328

처음에 작성한 코드와 AC를 받은 코드의 로직 자체는 비슷했지만 간단한 트릭을 요구하는 BFS(Breadth First Search) 알고리즘 문제였습니다.

처음에 작성한 코드는 테두리에 빈칸을 두지 않고 설계도를 그대로 입력받아 입구를 4개의 반복문을 찾으며 BFS를 시도했기 때문에 상당히 비효율적이였습니다.

하지만 앞서 언급한 트릭은 테두리를 빈 칸('*')으로 채우는 것이였습니다.

이렇게 한다면 반복문을 이용하는 대신 BFS(0, 0)을 호출함으로써 답을 쉽게 찾아낼 수 있습니다!

전체적인 알고리즘은 아래와 같습니다.

1. 설계도를 입력 받을 때 테두리를 빈 칸 . 으로 채웁니다.

2. 열쇠를 입력받으면 해당 열쇠로 열 수 있는 문을 미리 열어놓습니다.

3. 전형적인 BFS를 돌리는데 조건이 많기 때문에 기존에 작성한대로 BFS 함수를 작성하면 까다롭습니다. 따라서 해당 칸으로부터 4방향을 큐에다가 넣은 다음에 조건을 충족하지 못하면 continue하는 방식으로 코드를 작성하는 편이 쉽습니다.

4. 서류를 찾으면 document를 하나 증가시키고 빈 칸으로 바꿉니다(중복 탐지 방지), 그리고 열쇠를 찾으면 빈 칸으로 바꾸고 해당 열쇠가 기존에 갖고 있던 열쇠가 아닌 경우 2번처럼 해당 열쇠로 열 수 있는 문을 열어두고 다시 BFS를 시작합니다.

#include <iostream>

#include <string>

#include <queue>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100 + 2;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0} , {0, 1}, {0, -1} };

 

int H, W;

string bluePrint[MAX];

bool visited[MAX][MAX];

bool key[26];

int document;

 

void BFS(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] || bluePrint[curY][curX] == '*' || ('A' <= bluePrint[curY][curX] && bluePrint[curY][curX] <= 'Z'))

                         continue;

 

                 visited[curY][curX] = true; //방문 표시

 

                 //문서

                 if (bluePrint[curY][curX] == '$')

                 {

                         document++;

                         bluePrint[curY][curX] = '.';

                 }

                 //열쇠 찾았을 경우

                 if ('a' <= bluePrint[curY][curX] && bluePrint[curY][curX] <= 'z')

                 {

                         char door = (char)toupper(bluePrint[curY][curX]);

                         bluePrint[curY][curX] = '.';

 

                         //이미 있던 열쇠에 대해서는 처리하지 않는다

                         if (key[(int)door - 65] == false)

                         {

                                 key[(int)door - 65] = true;

                                 //잠긴 문을 연다

                                 for (int y = 1; y <= H; y++)

                                          for (int x = 1; x <= W; x++)

                                                  if (bluePrint[y][x] == door)

                                                          bluePrint[y][x] = '.';

                                 //잠긴 문이 열렸으므로 모든 경로를 다시 확인

                                 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 nextY = curY + moveDir[i].y;

                         int nextX = curX + moveDir[i].x;

 

                         q.push(make_pair(nextY, nextX));

                 }

        }

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

                 memset(key, false, sizeof(key));

                 for (int j = 0; j < MAX; j++)

                         bluePrint[j].clear();

                 memset(visited, false, sizeof(visited));

                 cin >> H >> W;

 

                 //테두리를 빈 칸으로

                 for (int j = 0; j < W + 2; j++)

                         bluePrint[0] += '.';

                 for (int j = 1; j <= H; j++)

                 {

                         string temp;

                         cin >> temp;

                         bluePrint[j] += '.';

                         bluePrint[j] += temp;

                         bluePrint[j] += '.';

                 }

                 for (int j = 0; j < W + 2; j++)

                         bluePrint[H + 1] += '.';

 

                 string alphabet;

                 cin >> alphabet;

 

                 for (int j = 0; alphabet[j] != '0' && j < alphabet.length(); j++)

                 {

                         key[(int)alphabet[j] - 97] = true; //열쇠 설정

                         //문을 열어둔다

                         for (int y = 1; y <= H; y++)

                                 for (int x = 1; x <= W; x++)

                                 {

                                          if (bluePrint[y][x] == (char)toupper(alphabet[j]))

                                                  bluePrint[y][x] = '.';

                                 }

                 }

 

                 document = 0;

                 BFS(0, 0);

                 cout << document << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~