[C++] 9328번 열쇠 - BFS

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX_LEN 105

using namespace std;

int T, h, w;  //테스트 케이스이 개수 T, 높이와 너비 h와 w
char map[MAX_LEN][MAX_LEN];  //맵
int key[30];  //알파벳의 개수는 26개
queue<pair<int, int>> q;  //좌표 저장
vector<pair<int, int>> ufkey[30];  //열지 못한 문. unfound key
char ks[30];

int xt[5] = {0, 1, 0, -1, 0};  //xturn
int yt[5] = {0, 0, -1, 0, 1};

int main()
{
    scanf("%d", &T);
    LOOP(i, T) {
        int cnt=0;
        
        scanf("%d %d\n", &h, &w);  //입력
        LOOP(j, h) {
            LOOP(k, w+1) {
                scanf("%c", &map[j][k]);
                if((j==1 || j==h || k==1 || k==w) && k!=w+1) {  //테두리에서 길 찾기
                    switch(map[j][k]) {
                        case '*':  //막혀있음
                            continue;
                        case '$':  //돈이 있음
                            cnt++;
                        case '.':  //아직 탐색하지 않음
                            q.push({j, k});  //큐에 추가
                            break;
                        default: {
                            int tmp = map[j][k];
                            
                            if(tmp>='a') {  //열쇠는 추가
                                key[tmp-'a']=1;
                                while(!ufkey[tmp-'a'].empty()) {
                                    q.push({ufkey[tmp-'a'].back().first, ufkey[tmp-'a'].back().second});
                                    ufkey[tmp-'a'].pop_back();
                                }
                                q.push({j, k});
                            }
                            else {  //문이
                                if(key[tmp-'A'])  //열쇠가 있다면 열고 큐에 추가
                                    q.push({j, k});
                                else {  //열쇠가 없으면 좌표 저장
                                    ufkey[tmp-'A'].push_back({j, k});
                                    map[j][k]='*';
                                }
                            }
                        }
                    }
                    map[j][k]='*';
                }
            }
        }
        
        scanf("%s", ks);
        if(ks[0]) {
            for(int i=0; ks[i]; i++) {
                key[ks[i]-'a']=1;
                while(!ufkey[ks[i]-'a'].empty()) {
                    q.push({ufkey[ks[i]-'a'].back().first, ufkey[ks[i]-'a'].back().second});
                    ufkey[ks[i]-'a'].pop_back();
                }
            }
        }
        
        while(!q.empty()) {  //더 이상 길이 없을 때까지 탐색
            int x = q.front().first, y = q.front().second;
            q.pop();
            //printf("%d %d\n", x, y);
            LOOP(i, 4) {
                int nx=x+xt[i], ny=y+yt[i];
                switch(map[nx][ny]) {
                    case '\n':
                    case 0:
                    case '*':  //막혀있음
                        continue;
                    case '$':  //돈이 있음
                        cnt++;
                    case '.':  //아직 탐색하지 않음
                        q.push({nx, ny});  //큐에 추가
                        break;
                    default: {
                        int tmp = map[nx][ny];
                        
                        if(tmp>='a') {  //열쇠는 추가
                            key[tmp-'a']=1;
                            while(!ufkey[tmp-'a'].empty()) {
                                q.push({ufkey[tmp-'a'].back().first, ufkey[tmp-'a'].back().second});
                                ufkey[tmp-'a'].pop_back();
                            }
                            q.push({nx, ny});
                        }
                        else {  //문이
                            if(key[tmp-'A'])  //열쇠가 있다면 열고 큐에 추가
                                q.push({nx, ny});
                            else  //열쇠가 없으면 좌표 저장
                                ufkey[tmp-'A'].push_back({nx, ny});
                        }
                    }
                }
                map[nx][ny]='*';
            }
        }
        LOOP(i, 30) ufkey[i-1].clear();
        memset(key, 0, sizeof(int)*30);
        
        cout << cnt << '\n';
    }
    
    return 0;
}

맨 처음에 짜다가 오류가 발생해서 덧 싀우고 덧 씌우다 보니 스파게티 코드가 되버렸다. ㅋㅋㅋㅋㅋ

 

<알고리즘>

1. 테두리 탐색하기.

2. 큐에서 하나씩 꺼내서 탐색하기

 

똑같은 방법으로 하는데 좋게 정리 된 코드가 있어서 가져왔다. (나는 귀찮)

 

<정리된 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/20511286

로그인

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.