[백준 2564] 경비원 C++

문제

백준 2564 경비원 C++

2564번: 경비원

풀이

이해는 바로 했는데 구현을 어떻게 할까 고민을 많이 했던 문제

최단 경로가 맞은편인지, 시계인지, 반시계인지 다 확인을 해줘야 하는데

if 문 덕지덕지 써가면서 각 케이스마다 모두 처리해 주기는 너무 싫었다.

그래서 좌상단을 0으로 기준을 잡고 시계방향(북->동->남->서)으로 각각의 좌표를 RoundPos로 명명하고 RoundPos를 잡아주었다.

이렇게 좌표를 잡아주면 문제 예시의 RoundPos는 다음과 같다.

 

1번 상점 좌표 : 북 4 / Round Pos : 4(왼쪽부터 북)

2번 상점 좌표 : 서 2 / Round Pos : 10(북) + 5(동) + 10(남) + 3(아래서부터 서) = 28

3번 상점 좌표 : 남 8 / Round Pos : 10(북) + 5(동) + 2(왼쪽부터 남) = 17

동근이 좌표 : 남 3 / Round Pos : 10 + 5 + 7 = 22

 

북->동->남->서의 시계 방향으로 갈 때, 사이 거리는 Round Pos의 차와 같다.

근데 반시계 방향으로 가는 게, 혹은 서->북으로 가는 게 더 가까울 수 있으므로 반시계 사이 거리와 비교해줘야 한다.

이 때는 시계 방향 거리 + 반시계 방향 거리 = 블록의 둘레라는 점을 이용한다.

따라서 반시계 방향 거리 = 블록의 둘레 - 시계 방향 거리이고, 반시계가 더 빠를 경우는 시계 방향 거리가 블록의 둘레의 절반 이상일 때이다.

즉, 최소 거리를 dist라고 하면 dist = min(시계 방향 거리, 블록 둘레 - 시계 방향 거리)이다.

 

예제의 동근이와 상점 거리를 이 방법대로 구하면 다음과 같다.

1번 <-> 동근 : 시계 방향은 18, 반시계는 30 - 18 = 12, 반시계 방향이 더 빠름

2번 <-> 동근 : 시계 방향은 6, 반시계는 24, 시계 방향가 더 빠름

3번 <-> 동근 : 시계 방향은 5, 반시계는 25, 시계 방향이 더 빠름

 

따라서 12 + 6 + 5 = 23이 나온다.

소스 코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
 
int calculRoundPos(int dir, int pos, int width, int height)
{
    int blockRound = 2 * (width + height);
    int roundPos = 0;
 
    switch (dir)
    {
        // 북
    case 1:
        roundPos = pos;
        break;
        // 남
    case 2:
        roundPos = blockRound - height - pos;
        break;
        // 서
    case 3:
        roundPos = blockRound - pos;
        break;
        // 동
    case 4:
        roundPos = width + pos;
        break;
    default:
        break;
    }
 
    return roundPos;
}
 
int main()
{
    int width = 0;
    int height = 0;
    cin >> width >> height;
 
    int cnt = 0;
    cin >> cnt;
    queue<pair<int, int>> storeInfo;
 
    while (cnt--)
    {
        int dir = 0;
        int pos = 0;
        cin >> dir >> pos;
        storeInfo.push({ dir, pos });
    }
 
    int startDir = 0;
    int startPos = 0;
    cin >> startDir >> startPos;
 
    int startRoundPos = calculRoundPos(startDir, startPos, width, height);
    int sum = 0;
    int blockRound = 2 * (width + height);
    
    while (!storeInfo.empty())
    {
        int storeDir = storeInfo.front().first;
        int storePos = storeInfo.front().second;
        storeInfo.pop();
 
        int storeRoundPos = calculRoundPos(storeDir, storePos, width, height);
        int dist = abs(startRoundPos - storeRoundPos);
 
        dist = min(dist, blockRound - dist);
 
        sum += dist;
    }
 
    cout << sum;
 
    return 0;
}