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

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

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드

---

01. 개요

출처

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

 

문제

 

입력

 

출력

예시

 

 

---

02. 접근 방식

 

요약

1. 구역에 대한 초기화 및 입력

2. 시작 지점(가장자리) 탐색

3. 시작 지점은 바닥, 열쇠, 문, 문서 모두 해당 가능하므로 조건에 따라 추가 처리

4. BFS로 각 구역마다 방문 → DFS도 충분히 가능

5. 문에 도착했지만 열쇠가 없다면, 대기 칸에 추가

6. 열쇠를 습득했다면, 해당 열쇠와 상호작용하는 문의 대기 칸에 있던 위치를 모두 queue에 추가

7. 만약에 문서를 습득했다면, 중복 처리를 방지하기 위해 일반 바닥(.)으로 변경

8. 습득한 문서 반환

과정

1. 구역에 대한 초기화 및 입력

구역의 최대 영역을 기준으로 할당을 합니다.

그리고, 새로운 테스트 케이스가 입력될 때마다 초기화를 진행합니다.

 

이때, 미리 할당할 데이터는 구역 정보, 열쇠 정보입니다.

구역은 [y 좌표][x 좌표]로 관리하고, 열쇠는 [열쇠 알파벳 - 'a']과 [문 알파벳 - 'A']로 접근할 수 있도록 합니다.

따라서, 구역은 100 * 100으로 할당하고, 열쇠는 알파벳의 개수인 26으로 할당합니다.

 

 

2. 시작 지점(가장자리) 탐색 및 추가 처리

시작 자리는 벽(*)이 아닌 경우에만 성립합니다.

따라서, 바닥, 열쇠, 문, 문서 모두 시작 지점이 될 수 있습니다.

 

1) 바닥 - 바로 queue에 넣으면 됩니다.

2) 문서 - 바닥(.)으로 변경한 뒤, 문서의 개수를 1 증가합니다.

3) 열쇠 - 해당 열쇠가 존재한다고 설정합니다.

4) 문 - 해당 열쇠의 존재 여부를 아직 확신할 수 없으므로, 열쇠의 대기칸에 추가합니다.

 

즉, 열쇠 정보는 열쇠 소유 여부의 bool 타입과 대기칸인 vector<Loc>의 구조체를 가지고 있어야 합니다.

여기서 Loc 타입은 단순히 int형의 y좌표와 x좌표를 가진 구조체입니다.

 

 

3. queue 시작 전, 소유하고 있는 열쇠에 대한 시작 지점의 문 처리

 

queue를 시작하기 전에, 열쇠와 문에 대한 사전 처리가 추가로 더 필요합니다.

구역에 대한 정보를 모두 입력하고, 소유하고 있는 열쇠의 정보도 입력합니다.

따라서, 소유하고 있는 열쇠로 시작 지점에 있는 문을 열 수 있는 경우도 존재합니다.

 

열쇠 정보를 반복문으로 모두 탐색해, 열쇠가 존재한다면, 해당 열쇠의 대기칸 좌표를 모두 queue에 넣습니다.

queue에 넣을 때는 현재 지점을 이미 방문했다고 처리해야 합니다.

 

 

4. BFS로 각 구역마다 방문 → DFS도 충분히 가능

 

BFS로 방문할 때, 현재 지점에서 상하좌우로만 이동할 수 있습니다.

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};

// ......
for(int dir = 0; dir < 4; dir++)
{
	int nextY = cur.y + dy[dir];
    	int nextX = cur.x + dx[dir];
        
        // TODO : 추가 검사
}

위 코드처럼, 방향에 대한 정보를 미리 입력하면, switch문보다 편하게 사용할 수 있습니다.

 

다음 지점에 대한 추가 검사를 진행해야 합니다.

 

1) 유효 범위 내에 존재 여부

2) 벽(*)인지 확인

3) 이미 방문했는지 확인

4) 문에 도착한 경우

  - 열쇠 O → 이동

  - 열쇠 X  → 대기 칸에서 대기

 

5) 열쇠인 경우

  - 이미 발견한 열쇠는 단순 이동

  - 새롭게 발견한 열쇠는 대기하고 있던 문들도 모두 개방 →대기칸의 좌표를 모두 queue에 추가

 

6) 문서인 경우

  - 문서 찾은 개수 증가

  - 이동

  - 바닥(.)으로 변경

 

7) 바닥인 경우

  - 단순 이동

 

5. 습득한 문서 개수 반환

 

queue가 비어있으면, 위 과정을 모두 마쳤으므로 찾은 문서 개수를 반환합니다.

 

---

03. 정답 코드

// 골드 1 - 9328번 : 열쇠
// 작성자 : free4760(jeonghoe22)

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

using namespace std;

const int MAX_KEY_COUNT = 26;

struct Loc
{
    int y = 0;
    int x = 0;
};

struct Key
{
    vector<Loc> locs;
    bool b_find = false;

    Key()
    {
        locs.reserve(10);
    }
};

struct Area
{
    Loc loc;
    bool b_visit = false;
    char state = ' ';
};

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};

vector<vector<Area>> g_areas;
vector<Key> g_keys;
queue<Loc> g_q;

// 구역 정보 초기화
void resetArea(const int h, const int w)
{
    for(int i = 0; i < h; i++)
    {
        for(int j = 0; j < w; j++)
        {
            g_areas[i][j].b_visit = false;
        }
    }
}

// 키 정보 초기화
void resetKey()
{
    for(int i = 0; i < MAX_KEY_COUNT; i++)
    {
        g_keys[i].b_find = false;
        g_keys[i].locs.clear();
    }
}

// 구역 정보 입력
void inputArea(const int h, const int w)
{
    string input;
    for(int i = 0; i < h; i++)
    {
        cin >> input;

        for(int j = 0; j < w; j++)
        {
            g_areas[i][j].state = input[j];
            
            // 밖에 있는 입구부터 추가
            if(input[j] != '*' && (i == 0 || j == 0 || i == h-1 || j == w-1))
            {
                // 1. 문인 경우는 일단 대기
                if(input[j] >= 'A' && input[j] <= 'Z')
                {
                    g_keys[input[j] - 'A'].locs.push_back({i, j});
                    continue;
                }

                // 2. 열쇠인 경우에는 열쇠 소유를 하고 있다고 처리
                if(input[j] >= 'a' && input[j] <= 'z')
                    g_keys[input[j] - 'a'].b_find = true; 
                
                // 3. 문서, 바닥인 경우에는 바로 추가 가능
                g_q.push({i, j});
                g_areas[i][j].b_visit = true;
            }
        }
    }
}

// 미리 소지하고 있는 키 정보 입력
void inputKey()
{
    string input;
    cin >> input;

    if(input == "0")
        return;

    for(const char& key : input)
    {
        g_keys[key - 'a'].b_find = true;
    }
}

// 경계 안에 있는지 확인
bool isInBoard(const int h, const int w, const int y, const int x)
{
    return x >= 0 && y >= 0 && y < h && x < w;
}

// 시뮬레이션 시작
int simulate(const int h, const int w)
{
    // 키를 미리 소지한 경우면서, 대기하고 있는 위치를 먼저 처리
    for(Key& key : g_keys)
    {
        if(key.b_find)
        {
            for(const Loc& loc : key.locs)
                g_q.push({loc.y, loc.x});

            key.locs.clear();
        }
    }

    int count = 0;

    while(g_q.empty() == false)
    {
        Loc cur = g_q.front();
        g_q.pop();

        // 현재 위치에 보물이 있는 경우(가장자리)
        if(g_areas[cur.y][cur.x].state == '$')
        {
            g_areas[cur.y][cur.x].state = '.';
            count++;
        }

        // 다음 위치에 대한 검사
        for(int dir = 0; dir < 4; dir++)
        {
            int nextY = cur.y + dy[dir];
            int nextX = cur.x + dx[dir];

            // 1. 범위 안에 있는지 확인
            if(isInBoard(h, w, nextY, nextX) == false)
                continue;

            Area& next = g_areas[nextY][nextX];

            // 2. 벽이 아닌지 확인
            if(next.state == '*')
                continue;

            // 3. 이미 방문했다면, 무시
            if(next.b_visit)
                continue;

            // 방문했다고 설정
            next.b_visit = true;

            // 4. 문이 있다면, 열쇠가 있는지 검사
            if(next.state >= 'A' && next.state <= 'Z')
            {
                // 해당 문을 열 수 있는 열쇠가 있다면, 이동
                if(g_keys[next.state - 'A'].b_find)
                    g_q.push({nextY, nextX});

                // 해당 문을 열 수 있는 열쇠가 없다면, 대기
                else
                    g_keys[next.state - 'A'].locs.push_back({nextY, nextX});
            
                continue;
            }

            // 5. 열쇠라면, 이동하고 현재 대기하고 있던 문들도 모두 열기
            if(next.state >= 'a' && next.state <= 'z')
            {
                g_q.push({nextY, nextX});

                // 이미 발견한 열쇠는 단순히 이동
                if(g_keys[next.state - 'a'].b_find)
                    continue;
                
                // 새롭게 발견한 열쇠는 대기하고 있던 문들도 모두 개방
                else
                {
                    g_keys[next.state - 'a'].b_find = true;

                    for(const Loc& loc : g_keys[next.state - 'a'].locs)
                    {
                        g_q.push({loc.y, loc.x});
                    }

                    g_keys[next.state - 'a'].locs.clear();
                    continue;
                }
            }

            // 6. 보물이라면, 숫자 증가
            if(next.state == '$')
            {
                next.state = '.';
                g_q.push({nextY, nextX});
                count++;
                continue;
            }

            // 7. 그냥 바닥인 경우 이동
            if(next.state == '.')
            {
                g_q.push({nextY, nextX});
            }
        }
    }

    return count;
}

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // 테스트 케이스 개수 T
    int T;
    cin >> T;

    g_areas = vector<vector<Area>>(100, vector<Area>(100));
    g_keys = vector<Key>(MAX_KEY_COUNT);

    int h, w;
    for(int i = 0; i < T; i++)
    {
        // 높이 h, 너비 w
        cin >> h >> w;

        inputArea(h, w);
        inputKey();

        cout << simulate(h, w) << "\n";

        resetArea(h, w);
        resetKey();
    }
}

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!