16461번 듀얼 채널 VHF 무전기

제 5회 한양대학교 프로그래밍 경시대회 Open Contest - Advanced Div. B번 문제

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

문제를 제대로 안 읽어서 살짝 고생했다.

주파수 조절은 세 가지 전략 중에서 하나를 선택하여 이루어진다.

2가지 풀이 방법이 있다.

① BFS - 내가 푼 방법

② 시뮬레이션 - 다른 분의 코드를 참고하였다.

① BFS

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
double A = 0.0, B = 0.0, goal = 0.0;
 
char now;
 
int down()
{
    queue<pair<int, char> > q;
 
    bool visit[2002] = { false, };
 
    memset(visit, false, sizeof(visit));
 
    // 현재 채널에 따라 경우의 수가 2가지로 나눌 수 있다.
    if (now == 'A')
    {
        q.push({ (int)A, now });
        visit[(int)A] = true;
 
    }
    else if (now == 'B')
    {
        q.push({ (int)B, now });
        visit[(int)B] = true;
    }
 
    int ret = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int present = q.front().first;
            char aorb = q.front().second;
 
            int var = present;
            // 밑에 연산에 의해 present가 변하므로, var을 활용한다.
 
            q.pop();
 
            if (present == (int)goal)
            {
                // 같으면 return
                return ret;
            }
 
            if (aorb == 'A')
            {
                // A/B
                aorb = 'B';
                present = (int)B;
                if (!visit[present])
                {
                    q.push({ present, aorb });
                    visit[present] = true;
                }
 
                // down
                aorb = 'A';
                present = var;
                present -= 20;
                if (present < 0) present = 2000;
                if (!visit[present])
                {
                    q.push({ present, aorb });
                    visit[present] = true;
                }
            }
            else if (aorb == 'B')
            {
                // A/B
                aorb = 'A';
                present = (int)A;
                if (!visit[present])
                {
                    q.push({ present, aorb });
                    visit[present] = true;
                }
 
                // down
                aorb = 'B';
                present = var;
                present -= 20;
                if (present < 0) present = 2000;
                if (!visit[present])
                {
                    q.push({ present, aorb });
                    visit[present] = true;
                }
            }
        }
 
        ++ret;
 
        // 어차피 최댓값이 6이므로, 6이상이 되면, 바로 return.
        if (ret >= 6) return ret;
    }
}
 
int up()
{
    queue<pair<int, char> > q;
 
    bool visit[2002] = { false, };
 
    memset(visit, false, sizeof(visit));
 
    // 현재 채널에 따라 경우의 수가 2가지로 나눌 수 있다.
    if (now == 'A')
    {
        q.push({ (int)A, now });
        visit[(int)A] = true;
 
    }
    else if (now == 'B')
    {
        q.push({ (int)B, now });
        visit[(int)B] = true;
    }
 
    int ret = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int present = q.front().first;
            char aorb = q.front().second;
 
            int var = present;
            // 밑에 연산에 의해 present가 변하므로, var을 활용한다.
 
            q.pop();
 
            if (present == (int)goal)
            {
                // 같으면 return
                return ret;
            }
 
            if (aorb == 'A')
            {
                // A/B
                aorb = 'B';
                present = (int)B;
                if (!visit[present])
                {
                    q.push({ present, aorb });
                    visit[present] = true;
                }
 
                // up
                aorb = 'A'; // 단순 up을 누르는 것이므로, 위와 달리 aorb = 'A'로 다시 설정
                present = var; // 초기 present를 저장해놨던 var 활용.(연산에 의해 변할 수 있기 때문)
                present += 20; // up은 +20
                if (present > 2000) present = 0;
                // 146.000(= 2000)을 초과하면, 그 반대편인 144.000(=0)으로 초기화.
                if (!visit[present])
                {
                    // 방문하지 않았다면
 
                    q.push({ present, aorb });
                    visit[present] = true;
                }
            }
            else if (aorb == 'B')
            {
                // A/B
                aorb = 'A';
                present = (int)A;
                if (!visit[present])
                {
                    q.push({ present, aorb });
                    visit[present] = true;
                }
 
                // up
                aorb = 'B';
                present = var;
                present += 20;
                if (present > 2000) present = 0;
                if (!visit[present])
                {
                    q.push({ present, aorb });
                    visit[present] = true;
                }
 
            }
        }
 
        ++ret;
 
        // 어차피 최댓값이 6이므로, 6이상이 되면, 바로 return.
        if (ret >= 6) return ret;
    }
}
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    for (int i = 0; i < T; i++)
    {
        scanf("%lf %lf %c %lf", &A, &B, &now, &goal);
 
        /*
        144.000 이상 ~ 146.000 이하이므로

        곱하기 1000을 하면
        144000 이상 ~ 146000이하

        빼기 144000
        0 이상 ~ 2000 이하 이므로,

        bool visit[2002]을 쉽게 이용할 수 있다.
        */
 
        A *= 1000;
        B *= 1000;
        goal *= 1000;
 
        A -= 144000;
        B -= 144000;
        goal -= 144000;
 
        int upcnt = up();
        int downcnt = down();
 
        int result = min(upcnt, downcnt);
 
        if (result >= 6) result = 6;
 
        // 6번까지가 최대이다. 어차피 6 이상은 번호를 직접 6개를 누를 수 있기 때문이다.
        if (result >= 6) printf("6\n");
        else printf("%d\n", result);
    }
 
    return 0;
}

② 시뮬레이션

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
double A = 0.0, B = 0.0, goal = 0.0;
 
char now;
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    while(T--)
    {
        scanf("%lf %lf %c %lf", &A, &B, &now, &goal);
 
        int MAX = 6;
 
        A *= 1000;
        B *= 1000;
        goal *= 1000;
 
        int cnt1 = 0;
        int cnt2 = 0;
 
        if (now == 'A') ++cnt2; // A/B버튼을 눌러서 B로 이동하는 경우의 수 
        else if (now == 'B') ++cnt1; // A/B버튼을 눌러서 A로 이동하는 경우의 수
 
        // A에서 출발
        // (now가 A일 때, A/B버튼을 안 누른 경우)
        // (now가 B일 때, A/B버튼을 누른 경우)
 
        int a = (int)A;
        int b = (int)A;
        int g = (int)goal;
 
        for (int i = 0; i < 6; i++)
        {
            if (a == g)
            {
                MAX = min(MAX, cnt1);
            }
 
            a += 20;
 
            if (a > 146000) a = 144000;
 
            if (b == g)
            {
                MAX = min(MAX, cnt1);
            }
 
            b -= 20;
 
            if (b < 144000) b = 146000;
 
            ++cnt1;
        }
 
        // B에서 출발
        // (now가 B일 때, A/B버튼을 안 누른 경우)
        // (now가 A일 때, A/B버튼을 누른 경우)
        
        a = (int)B;
        b = (int)B;
        g = (int)goal;
 
        for (int i = 0; i < 6; i++)
        {
            if (a == g)
            {
                MAX = min(MAX, cnt2);
            }
 
            a += 20;
 
            if (a > 146000) a = 144000;
 
            if (b == g)
            {
                MAX = min(MAX, cnt2);
            }
 
            b -= 20;
 
            if (b < 144000) b = 146000;
 
            ++cnt2;
        }
 
        printf("%d\n", MAX);
    }
 
    return 0;
}