인프런 커뮤니티 질문&답변

안녕하세요 동훈님 ㅎㅎ

코드리뷰를 드리면요.

1. map의 경우 if(mp[0]) 이렇게 참조하는 순간 mp[0] = 0이 할당이 됩니다. 이부분을 신경써서 다시 로직을 구축해야 하구요.

2. 굳이 이렇게 q.size를 나눠서 할필요는 없습니다.

    while(!q.empty()){
        int size = q.size();
        cnt++;
        while(size--){
            pair<int,int> now = q.front();

어차피 visited에 상태값이 담기니까요.

3. 실수유발 가능성이 높은 코드.

            for (int i = 0; i < 8; i++){
                
                if (i == 0){ //a 채우기

이런 중첩 if문은 실수를 유발합니다.

그래서!

제가 한번 다듬어 봤는데요.

이렇게 한번 해보시겠어요?

#include<bits/stdc++.h>
using namespace std;

int a, b, c, d;
map<pair<int, int>, int> visited;

pair<int, int> moveab(int a_cnt, int b_cnt) {
    if (a_cnt > b - b_cnt) {
        a_cnt -= b - b_cnt;
        b_cnt = b;
    } else {
        b_cnt += a_cnt;
        a_cnt = 0;
    }
    return {a_cnt, b_cnt};
}

pair<int, int> moveba(int a_cnt, int b_cnt) {
    if (b_cnt > a - a_cnt) {
        b_cnt -= a - a_cnt;
        a_cnt = a;
    } else {
        a_cnt += b_cnt;
        b_cnt = 0;
    }
    return {a_cnt, b_cnt};
}

int bfs() {
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[{0, 0}] = 0;

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

        if (now.first == c && now.second == d) {
            return visited[now];
        }

        vector<pair<int, int>> next_states = {
            {a, now.second}, {now.first, b},
            {0, now.second}, {now.first, 0},
            moveab(now.first, now.second),
            moveba(now.first, now.second)
        };

        for (auto& state : next_states) {
            if (!visited.count(state)) {
                visited[state] = visited[now] + 1;
                q.push(state);
            }
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> a >> b >> c >> d;
    int result = bfs();
    cout << result << "\n";
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.