[백준] 2564 - 경비원 (C++)

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

경비원 동근이가 담당하고 있는 곳은 직사각형 모양의 블록으로 블록 중간을 가로질러 차가 통과할 수 없다. 이 블록 경계에 무인 경비를 의뢰한 상점들이 있다.

예를 들어, 1번 상점에서 호출이 들어왔을 때 동근이가 블록을 시계방향으로 돌아 이동하면 이동 거리가 12가 된다. 반면 반시계방향으로 돌아 이동하면 이동 거리는 18이 된다. 따라서 동근이가 1번 상점으로 가는 최단 거리는 12가 된다. 마찬가지로 동근이의 위치에서 2번 상점까지의 최단 거리는 6, 3번 상점까지의 최단 거리는 5가 된다.

 

블록의 크기와 상점의 개수 및 위치, 그리고 동근이의 위치가 주어질 때 동근이의 위치와 각 상점 사이의 최단 거리의 합을 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ 블록의 가로 길이, 세로 길이, 상점의 개수 ≤ 100
• 상점의 위치 = [dir, num]
  • dir은 상점이 위치한 방향을 나타내는데, 1은 북쪽, 2는 남쪽, 3은 서쪽, 4는 동쪽에 상점이 있음을 의미한다.
  • num은 상점이 블록의 북쪽 또는 남쪽에 위치한 경우, 블록의 왼쪽 경계로부터의 거리를 나타내고, 상점이 블록의 동쪽 또는 서쪽에 위치한 경우, 위쪽 경계로부터의 거리를 나타낸다.
  • 동근이의 위치도 같은 방식으로 주어진다.
  • 상점이나 동근이의 위치는 블록의 꼭짓점이 될 수 없다.

 

아래처럼 가로의 길이가 10, 세로의 길이가 5인 블록이 존재할 때, 블록의 좌측 위의 좌표가 0인 수직선(북-동-남-서)으로 생각하고 쭉 펴 보면 동근이와 상점의 위치를 좌표로 나타낼 수 있다.

방향과 거리가 [dir, num]으로 주어질 때

• dir==1인 경우, 위치가 북쪽에 있으므로 좌표는 num으로 나타낼 수 있다.
• dir==4인 경우, 위치가 동쪽에 있으므로 좌표는 가로의 길이 + 가로의 길이로 나타낼 수 있다.
• dir==2인 경우, 위치가 남쪽에 있으므로 좌표가 가로의 길이 + 세로의 길이 + 가로의 길이 - num으로 나타낼 수 있다.
• dir==3인 경우, 위치가 서쪽에 있으므로 좌표는 가로의 길이 + 세로의 길이 + 가로의 길이 + 세로의 길이 - num으로 나타낼 수 있다.

 

상점과 동근이의 위치를 수직선 위의 좌표로 나타내고, 두 위치의 차이를 구하면 거리를 구할 수 있다. 이때 시계방향과 반시계방향으로 이동할 수 있으므로 두 가지 방법 중 최솟값을 더해가며 정답을 구하면 된다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. 가로의 길이, 세로의 길이, 상점의 개수 입력받기
2. 상점이 위치한 방향과 블록의 왼쪽(위쪽) 경계로부터의 거리 입력받기
   1. 좌측 위를 0으로 놓고 시계방향으로 돌 때, 방향과 거리에 따라 정수로 변환해 vector에 저장하기
3. 동근이 위치의 방향과 블록의 왼쪽(위쪽) 경계로부터의 거리 입력받기
   1. 상점과 동일한 방식으로 정수로 변환한 값을 변수에 저장하기
4. 반복문을 상점 개수만큼 돌리면서 동근이의 위치를 정수로 변환한 값과 상점의 위치를 정수로 변환한 값의 차이를 구하기
   1. 직사각형에서 이동 방법은 2가지이므로, 시계방향으로 이동했을 때와 반시계방향으로 이동했을 때 둘 중 최솟값을 ans에 더하면서 진행하기
5. ans 값 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해 보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

1~2회차

• 많은 조건 분기로 나눠서 풀려고 했는데 반례를 찾지 못해서 알고리즘을 수정함

#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int,int>
using namespace std;

int x,y,n,a,d,ans;
vector<pii> v;

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

    cin >> y >> x >> n;
    for (int i=0; i<n; i++) {
        cin >> d >> a;
        v.push_back({d,a});
    }
    cin >> d >> a;

    for (int i=0; i<n; i++) {
        auto [vd,va] = v[i];
        if (d==vd)
            ans += abs(va-a);
        else if (d+vd==3) // 북->남 or 남->북
            ans += min(y-a+y-va,a+va) + x;
        else if (d+vd==7) // 동->서 or 서->동
            ans += min(x-a+x-va,a+va) + y;
        else if (d==2&&vd==3 || d==3&&vd==2) // 남->서 or 서->남
            ans += a+va+1;
        else if (d==1&&vd==4 || d==4&&vd==1) // 북->동 or 동->북
            ans += y-a+x-va;
        else if (d==2&&vd==4) // 남->동
            ans += y-a+va;
        else if (d==4&&vd==2) // 동->남
            ans += a+y-va;
        else if (d==1&&vd==3) // 북->서
            ans += a+x-va;
        else if (d==3&&vd==1) // 서->북
            ans += x-a+va;
    }
    cout << ans;
}

 

---

정답 코드

#include <iostream>
#include <vector>
using namespace std;

int x,y,n,a,d,dg,ans;
vector<int> v;

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

    cin >> x >> y >> n;
    for (int i=0; i<n; i++) {
        cin >> d >> a;
        if (d==1) v.push_back(a);
        else if (d==4) v.push_back(a+x);
        else if (d==2) v.push_back(x-a+x+y);
        else v.push_back(y-a+2*x+y);
    }
    cin >> d >> a;
    if (d==1) dg = a;
    else if (d==4) dg = a+x;
    else if (d==2) dg = x-a+x+y;
    else dg = y-a+2*x+y;

    for (int i=0; i<n; i++) {
        int tmp = abs(v[i]-dg);
        ans += min(tmp,2*x+2*y-tmp);
    }
    cout << ans;
}