백준 14867번 물통

문제 링크입니다: https://www.acmicpc.net/problem/14867

BFS(Breadth First Search) 알고리즘을 적용하여 푸는 간단한 문제였지만 물통에 들어갈 수 있는 최대 양이 100,000이기 때문에 이차원 배열을 통해 visited를 표현할 수 없습니다.

따라서, map을 이용해서 visited를 표현하는데 처음 두 정보는 A와 B 물통에 들어있는 물의 양, 그리고 마지막 정보에는 현재단계까지 도달하는데 걸린 횟수를 저장하면 쉽게 풀 수 있습니다.

처음에는 조건부 연산자를 이용하여 M 단계에서 물을 이동한 후 newA와 newB를 저장했는데 시간초과가 발생했습니다.

따라서, if else문을 통해 newA와 newB를 저장하였더니 AC를 받은 것으로 보아 조건부 연산자를 사용하면 시간이 오래 걸리는 것 같습니다...

#include <iostream>

#include <queue>

#include <map>

#include <algorithm>

using namespace std;

 

int a, b, c, d;

map<pair<int, int>, int> visited; //A, B, cnt

 

int BFS(void)

{

        queue<pair<int, int>> q;

        q.push(make_pair(0, 0));

        visited[make_pair(0, 0)] = 0;

 

        //모든 행위의 순서는 A부터 그 다음 B

        while (!q.empty())

        {

                 int A = q.front().first;

                 int B = q.front().second;

                 int cnt = visited[make_pair(A, B)];

                 q.pop();

 

                 if (A == c && B == d)

                         return cnt;

 

                 //F

                 if (visited.count(make_pair(a, B)) == 0)

                 {

                         q.push(make_pair(a, B));

                         visited[make_pair(a, B)] = cnt + 1;

                 }

                 if (visited.count(make_pair(A, b)) == 0)

                 {

                         q.push(make_pair(A, b));

                         visited[make_pair(A, b)] = cnt + 1;

                 }

                 //E

                 if (visited.count(make_pair(0, B)) == 0)

                 {

                         q.push(make_pair(0, B));

                         visited[make_pair(0, B)] = cnt + 1;

                 }

                 if (visited.count(make_pair(A, 0)) == 0)

                 {

                         q.push(make_pair(A, 0));

                         visited[make_pair(A, 0)] = cnt + 1;

                 }

                 //M

                 int newA, newB;

                 //A > b - B ? newA = A + B - b, newB = b : newA = 0, newB = A + B;

                 if (A > b - B)

                 {

                         newA = A + B - b;

                         newB = b;

                 }

                 else

                 {

                         newA = 0;

                         newB = A + B;

                 }

                 if (visited.count(make_pair(newA, newB)) == 0)

                 {

                         q.push(make_pair(newA, newB));

                         visited[make_pair(newA, newB)] = cnt + 1;

                 }

                 //B > a - A ? newA = a, newB = B + A - a : newA = A + B, newB = 0;

                 if (B > a - A)

                 {

                         newA = a;

                         newB = B + A - a;

                 }

                 else

                 {

                         newA = A + B;

                         newB = 0;

                 }

                 if (visited.count(make_pair(newA, newB)) == 0)

                 {

                         q.push(make_pair(newA, newB));

                         visited[make_pair(newA, newB)] = cnt + 1;

                 }

        }

        return -1;

}

 

int main(void)

{

        cin >> a >> b;

        cin >> c >> d;

 

        cout << BFS() << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~