[백준/Baekjoon] 1194 달이 차오른다, 가자. C++ :: BFS & Implementation

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

1194번: 달이 차오른다, 가자.

---

1. Logic

열쇠가 6개밖에 없기때문에 비트로 표현 가능하다.

큐에 현재 열쇠를 모은 상태를 비트로 저장해서 관리해준다. 

 

이 문제에서 나눠질 부분문제를 생각해보면

1. 열쇠를 만날경우

- 현재 열쇠를 모은거와 지금 열쇠를 or연산하여 모은 상태를 구하고 모았던 열쇠면 다시 갈 필요 없기 때문에 건너뛰고 안모은 열쇠면 갱신한 열쇠 컬렉션 상태를 큐에 넣어준다.

2. 문을 만날경우

- 현재 가지고 있는 열쇠와 대조 후 문과 일치하는 열쇠가 있으면 문을 열고 들어간다.

3. 그냥 길일경우

방문하지 않았으면 진입한다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

char graph[51][51];
bool vis[51][51][1<<6];

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

int r, c;
int sy, sx;

void bfs() {
    queue<pair<pair<int, int>, pair<int, int>>> q;
    
    q.push({{sy, sx}, {0, 0}});
    
    while(!q.empty()) {
        int x = q.front().first.second;
        int y = q.front().first.first;
        int curCnt = q.front().second.first;
        int keyInfo = q.front().second.second;
        
        if(graph[y][x] == '1') {
            cout << curCnt;
            return;
        }
        
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || nx >= c || ny < 0 || ny >= r) continue;
            if(graph[ny][nx] == '#')continue;
            
            
            // 문
            if(graph[ny][nx] >= 'A' && graph[ny][nx] <= 'F') {
                //문 비트로 변환
                int roomNum = graph[ny][nx] - 'A';
                //문이랑 열쇠랑 대조
                bool check = keyInfo & (1 << roomNum);
                if(!check || vis[ny][nx][keyInfo]) continue;
                
                vis[ny][nx][keyInfo] = true;
                q.push({{ny, nx}, {curCnt+1, keyInfo}});
            }
            //열쇠
            else if(graph[ny][nx] >= 'a' && graph[ny][nx] <= 'f') {
                //열쇠 모은거에 지금 열쇠 합치기
                int newKeyInfo = keyInfo | (1 << (graph[ny][nx]-'a'));
                //이 열쇠 방문했었으면 안가기
                if(vis[ny][nx][newKeyInfo]) continue;
                
                q.push({{ny, nx}, {curCnt+1, newKeyInfo}});
                vis[ny][nx][newKeyInfo] = true;
            }
            else {
                if(vis[ny][nx][keyInfo]) continue;
                q.push({{ny, nx}, {curCnt+1, keyInfo}});
                vis[ny][nx][keyInfo] = true;
            }
        }
    }
    cout << -1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> r >> c;
    
    for(int i = 0 ; i < r; i++) {
        for(int j = 0; j < c; j++) {
            cin >> graph[i][j];
            if(graph[i][j] == '0') {
                sy = i;
                sx = j;
            }
        }
    }
    
    bfs();
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐