백준 g1 9328 열쇠 c++

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

9328번: 열쇠

 

문제 간단히 설명

• input
  • 맵에 벽, 대문자(자물쇠), 소문자(열쇠), $(먹어야 할 문서)
  • 갖고 있는 열쇠
• output
  • 최대로 먹을 수 있는 문서의 개수
• 대문자 자물쇠는 소문자 열쇠로 열 수 있음
• 출발점은 건물 가장자리 아무데나

풀이

1. 갖고 있는 열쇠로 열 수 있는 곳은 모두 뚫어놓기

2. bfs로 건물 안 열쇠&문서 주워먹기

 

1~2를 반복한다. 다만

1) 새로운 열쇠를 먹었을 때만 && 새로운 공간이 열렸을 때만 탐색을 하고, 

2) 새로 뚫은 지점만 다음 loop에 탐색하기
     - 새로 뚫은 지점만 탐색하면, 반복을 계속 해도 O(HW)가 되기 때문에 시간복잡도를 줄일 수 있음

 

도움이 되었던 반례 (실수했던 것)

https://www.acmicpc.net/board/view/127396

맨 처음 시작할 때 .뿐만 아니라 $, A, a 인 경우 모두 고려해야 한다.

 

수도 코드

while(!new_key)
	//1. 열 수 있는 곳은 뚫어 놓기
	useKey();
	if 새로 뚫은 곳이 없으면 break
    
	//2. bfs로 열쇠 먹기& 문서 먹기
	new_key = bfs() || new_key
    

newKey() {
	for (i, j: board)
    	if (board(i, j)가 대문자 && 해당하는 key를 가지고 있으면)
        	board(i, j) = '.' 빈 공간으로 바꾸기
            
            //새로 뚫린 공간에 접근할 수 있으면
            if 새로 뚫린 공간이 가장자리이거나, 인접한 위치에 vis가 1이면
            	vis(i, j) = 1
            	Q.push(i, j)
}

 

 

 

 

실제 풀이는 맨 처음 loop를 돌 때 처리를 더럽게 해서 코드가 좀 복잡하다

맨 처음에는 Q.push와 new_space를 따로 해주기 때문에, first 변수를 사용해서 while문 안에서 구분해주었다. 

/*boj g1 9328 열쇠*/
#include <iostream>
#include <queue>

#define MAXN 105
using namespace std;

int T, N, M;
string board[MAXN];
bool key[26];
int vis[MAXN][MAXN];
int answer = 0;
queue<pair<int, int>> Q;
bool first = true;

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

void printVis() {
    cout << "=================\n";
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << vis[i][j] << " ";
        }
        cout << "\n";
    }
}

void initialize() {
    for (int i = 0; i < 26; i++)
        key[i] = 0;
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            vis[i][j] = 0;
        }
    }

    answer = 0;
    first = true;

    while (!Q.empty())
        Q.pop();
}

void input() {
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        cin >> board[i];
    }

    string keyString;
    cin >> keyString;
    if (keyString != "0") {
        for (char a : keyString) {
            key[a - 'a'] = true;
        }
    }
}

bool useKey() {
    bool new_space = false;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] >= 'A' && board[i][j] <= 'Z') {
                int locker = board[i][j] - 'A';

                if (key[locker] == 1) {
                    board[i][j] = '.';

                    // 새로 뚫린 new_space가 가장자리이거나, vis==1과 근접해있으면 새로운 Q에 push
                    if (vis[i][j] != 1) {
                        if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
                            vis[i][j] = 1;
                            Q.push({i, j});
                            new_space = true;
                            continue;
                        }

                        bool flag = false;
                        for (int dir = 0; dir < 4; dir++) {
                            int nx = i + dx[dir];
                            int ny = j + dy[dir];

                            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;

                            if (vis[nx][ny] > 0) {
                                flag = true;
                                break;
                            }
                        }

                        if (flag) {
                            Q.push({i, j});
                            vis[i][j] = 1;
                            new_space = true;
                        }
                    }
                }
            }
        }
    }

    return new_space;
}

bool bfs() {
    bool flag = false;

    while (!Q.empty()) {
        pair<int, int> cur = Q.front();
        Q.pop();

        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (vis[nx][ny] > 0) continue;
            if (board[nx][ny] == '$') {
                answer++;
                board[nx][ny] == '.';

                vis[nx][ny] = 1;
                Q.push({nx, ny});
            } else if (board[nx][ny] == '.') {
                vis[nx][ny] = 1;
                Q.push({nx, ny});
            } else if (board[nx][ny] >= 'a' && board[nx][ny] <= 'z') {
                key[board[nx][ny] - 'a'] = 1;
                board[nx][ny] = '.';
                flag = true;

                vis[nx][ny] = 1;
                Q.push({nx, ny});
            } else
                continue; //* 나 대문자일 때
        }
    }

    return flag;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;

    while (T--) {
        initialize();
        input();
        useKey();

        // 맨 처음 Q
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (i == 0 || j == 0 || i == N - 1 || j == M - 1) {
                    if (board[i][j] == '.') {
                        vis[i][j] = 1;
                        Q.push({i, j});
                    }

                    else if (board[i][j] == '$') {
                        answer++;
                        vis[i][j] = 1;
                        Q.push({i, j});
                        board[i][j] = '.';
                    }

                    else if (board[i][j] >= 'a' && board[i][j] <= 'z') {
                        key[board[i][j] - 'a'] = 1;
                        vis[i][j] = 1;
                        Q.push({i, j});
                        board[i][j] = '.';
                    }
                }
            }
        }

        useKey();

        bool new_key = true;
        while (new_key) {
            // 0. 초기화
            new_key = false;

            // 1. 새로운 열쇠로 뚫어 놓기
            if (!first) {
                bool new_space = useKey();

                // 새로 열린 공간이 없다면 break
                if (!new_space) break;
            }

            // 2. bfs로 열쇠 & 문서 먹기
            new_key = new_key || bfs();

            first = false;
            // printVis();
        }

        cout << answer << "\n";
    }
}

 

새로 알게 된 것

1. cin.get 말고 string으로 board 받기

기존에는 int [N][N] 배열에다 cin.get()으로 하나하나 받았으나

string[N] 배열에다가 string 단위로 받으면 코드 양도 줄어들고 간편하다.