cyj893

저장소

백준: Class 5 - 9328

3 분 소요


</br> 클래스 5 계속
</br>

9328: 열쇠

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

void bfs(int nowx, int nowy){
    bool chk = false, f = false;
    for(int i = 0; i < 4; i++){
        if( canGo[nowx+dx[i]][nowy+dy[i]] == 1 ){
            chk = true;
            break;
        }
    }
    if( nowx == 0 || nowy == 0 || nowx == h-1 || nowy == w-1 ) f = true;
    if( !f && chk == false ) return;

    stack<int> keys;
    queue< pair<int, int> > q;
    q.push(make_pair(nowx, nowy));
    canGo[nowx][nowy] = 1;
    while( q.size() ){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if( 'a' <= mmap[x][y] && mmap[x][y] <= 'z' ){
            keys.push(mmap[x][y]-'a');
            mmap[x][y] = '.';
        }
        if( mmap[x][y] == '$' ){
            ans++;
            mmap[x][y] = '.';
        }
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if( nx < 0 || h <= nx || ny < 0 || w <= ny ) continue;
            if( 'A' <= mmap[nx][ny] && mmap[nx][ny] <= 'Z' ) continue;
            if( canGo[nx][ny] != 1 && mmap[nx][ny] != '*' ){
                q.push(make_pair(nx, ny));
                canGo[nx][ny] = 1;
            }
        }
    }
    while( keys.size() ){
        openDoors(keys.top());
        keys.pop();
    }

}

void openDoors(int c){
    for(int j = 0; j < doors[c].size(); j++){
        mmap[doors[c][j].first][doors[c][j].second] = '.';
        bfs(doors[c][j].first, doors[c][j].second);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while( t-- ){
        cin >> h >> w;
        ans = 0;
        for(int i = 0; i < 26; i++){
            doors[i].clear();
        }
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                cin >> mmap[i][j];
                if( 'A' <= mmap[i][j] && mmap[i][j] <= 'Z' )
                    doors[mmap[i][j]-'A'].push_back(make_pair(i, j));
                canGo[i][j] = 0;
            }
        }
        for(int i = 0; i < h; i++){
            if( canGo[i][0] == 0 && mmap[i][0] != '*'
                && (mmap[i][0] < 'A' || 'Z' < mmap[i][0]) ) bfs(i, 0);
            if( canGo[i][w-1] == 0 && mmap[i][w-1] != '*'
                && (mmap[i][w-1] < 'A' || 'Z' < mmap[i][w-1]) ) bfs(i, w-1);
        }
        for(int i = 0; i < w; i++){
            if( canGo[0][i] == 0 && mmap[0][i] != '*'
                && (mmap[0][i] < 'A' || 'Z' < mmap[0][i]) ) bfs(0, i);
            if( canGo[h-1][i] == 0 && mmap[h-1][i] != '*'
                && (mmap[h-1][i] < 'A' || 'Z' < mmap[h-1][i]) ) bfs(h-1, i);
        }
        string s;
        cin >> s;
        if( s != "0" ){
            for(int i = 0; i < s.size(); i++){
                openDoors(s[i]-'a');
            }
        }
        cout << ans << '\n';
    }
}

재밌는 구현 문제다
내가 생각한 순서는

  1. 일단 갈 수 있는 곳을 bfs()로 다 표시해 둔다(canGo[][]).
  2. 열쇠가 있다면 해당 문들을 다 연다(openDoors()).
  3. 문을 열었는데, 만약 그 곳이 갈 수 있는 곳과 연결된 곳이라면(즉 빌딩 밖과 연결 되었거나, 상하좌우 중 canGo[][] == 1가 있어서 그 문에도 갈 수 있으면) bfs()를 시행한다
  4. 거기서 또 열쇠나 문서를 얻을 거고, 열쇠가 있으면 또 2~4를 반복한다

이렇게 짜니까 잘 돌아 가더라.
갈 수 있는 곳을 표시해 두는 이유는 같은 bfs를 계속 하는 걸 방지하려고…
doors[] 벡터 배열은, 해당 알파벳 문들의 위치를 저장한다.

ex) 백준 예제
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz

처음, 일단 갈 수 있는 곳 체크
00000000000000000
11111111111110000
00000000000000001
00000000000000000
00000000000000000


그 다음, c로 문 C를 열기
C는 갈 수 있는 곳과 연결 되어 있으므로 bfs 시행, 열쇠 p 획득
******* * *********
....... . .....**$*
*B*A*P*[C]**X*Y*.X.
*y*x*a* p **$*$**$*
******* * *********

00000000000000000
11111111111110000
00000001000000001
00000001000000000
00000000000000000


p로 문 P를 열기
P는 갈 수 있는 곳과 연결 되어 있으므로 bfs 시행, 열쇠 a 획득
***** * ***********
..... . .......**$*
*B*A*[P]*.**X*Y*.X.
*y*x* a *.**$*$**$*
***** * ***********

00000000000000000
11111111111110000
00000101000000001
00000101000000000
00000000000000000


a로 문 A를 열기
A는 갈 수 있는 곳과 연결 되어 있으므로 bfs 시행, 열쇠 x 획득
*** * *************
... . .........**$*
*B*[A]*.*.**X*Y*.X.
*y* x *.*.**$*$**$*
*** * *************

00000000000000000
11111111111110000
00010101000000001
00010101000000000
00000000000000000


x로 문 X를 열기
X는 갈 수 있는 곳과 연결 되어 있으므로 bfs 시행, 문서 $ 1개 획득
********** * ******
.......... . ..**$*
*B*.*.*.**[X]*Y*.X.
*y*.*.*.** $ *$**$*
********** * ******

00000000000000000
11111111111110000
00010101001000001
00010101001000000
00000000000000000

x로 문 X를 열기
X는 갈 수 있는 곳과 연결 되어 있으므로 bfs 시행, 문서 $ 2개 획득
*************** * *
.............** $ *
*B*.*.*.**.*Y*.[X].
*y*.*.*.**.*$** $ *
*************** * *

00000000000000000
11111111111110000
00010101001000001
00010101001000000
00000000000000000

종료


</br>

요새 문제마다 너무 길어 져서 그냥 포스트 하나 당 문제 하나로 해야 겠다
</br>

댓글남기기

참고