[백준/Baekjoon] 17244 아맞다우산 C++ :: BFS

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

17244번: 아맞다우산

---

1. Logic

입력을 받은 후 물건이 있는 좌표를 받으면 0~5까지의 char타입으로 변경해서 넣어줬다.

BFS를 돌면서 입력 받을 때 char타입으로 변경해서 넣어준 물건을 만나면 다시 int타입으로 변경해서 shift연산을 통해 비트계산을 해서 몇번째 물건을 집었는지 기록한다.

BFS를 돌면서 E(출구)를 만났을 때 내가 받은 물건과 도착한 시점에서의 물건갯수가 일치하면 걸린시간을 리턴한다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int r, c;
int sy, sx;

int thingCnt=0;

char room[51][51];
int vis[51][51][1 << 5];

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

int bfs() {
    queue<pair<pair<int, int>, pair<int, int>>> q;
    
    q.push({{sy, sx}, {0, 0}});
    vis[sy][sx][0] = true;
    
    while(!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int cost = q.front().second.first;
        int thing = q.front().second.second;
        
        q.pop();
        
        if(room[y][x] == 'E') {
            if(thing == thingCnt) {
                return cost;
            }
        }
        
        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(room[ny][nx] == '#') continue;
            
            if(room[ny][nx] >= '0' && room[ny][nx] <= '4') {
                int newThingState = thing | (1 << (room[ny][nx]-'0'));
                
                if(vis[ny][nx][newThingState]) continue;
                
                q.push({{ny, nx}, {cost+1, newThingState}});
                vis[ny][nx][newThingState] = true;
            }
            else {
                if(vis[ny][nx][thing]) continue;
                
                q.push({{ny, nx}, {cost+1, thing}});
                vis[ny][nx][thing] = true;
            }
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> c >> r;
    
    int cnt = 0;
    
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            cin >> room[i][j];
            if(room[i][j] == 'S') {
                sy = i;
                sx = j;
                room[i][j] == '.';
            }
            else if(room[i][j] == 'X') {
                room[i][j] = cnt+'0';
                thingCnt = thingCnt | (1 << cnt);
                cnt++;
            }
        }
    }
    
    cout << bfs();
}

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

728x90