[백준] 30052번: 거리 두기 게임 [C/C++]

# 문제

30052번: 거리 두기 게임
https://www.acmicpc.net/problem/30052

30052번: 거리 두기 게임

---

# 접근

문제에서 제시된 게임을 좀 더 간단히 생각해 보자.
준성이는 두 말 사이의 거리가 최대한 작도록, 효석이는 크도록 해야 한다.
효석이가 말을 어디에 두어도 자신의 말과의 거리가 D 미만이 되게 하려면, 준성이는 최대한 격자판의 가운데에 자신의 말을 놓는 것이 최선의 선택이다. 반대로 효석이는 최대한 가장자리에 말을 두어야 한다.
 
특정 경우에선 준성이가 말을 최선의 선택으로 두었을 경우 효석이는 어디에 말을 두던 두 말 사이 거리가 D 미만이 될 수 있다. 게임판 모양이 원이라고 가정해 보자.

위 이미지에서 게임판은 반지름이 5인 원이고, D는 7이다. 만약 준성이가 말을 가운데에 둔다면, 효석이는 어디에 말을 두어도 두 말 사이의 거리는 D 미만이 된다.

따라서 효석이는 위처럼 준성이가 말을 두기 전 말을 둘 수 없는 구역을 지정해 두 말 사이의 거리가 D를 넘도록 할 수 있다. 우리가 알고 싶은 것은 효석이가 이기기 위해 필요한 최소한의 금지 구역이다.
 
위를 통해
1. 어떤 상황에도 효석이가 둘 수 있는 최적의 자리는 격자판의 가장자리, 즉 직사각형의 4개의 꼭짓점이다.
2. 어떤 칸에 준성이가 두었을 때, 효석이가 최적의 자리에 두어도 두 말 사이의 거리가 D 미만이 되는 칸은 효석이가 필수로 말을 둘 수 없도록 설정해야 하는 칸이다.
라는 것을 알 수 있다. 즉 우리는 4개의 꼭짓점과의 택시 거리가 모두 D 미만인 칸의 개수를 세면 된다.

---

# 풀이

#include <stdio.h>

int abs(int a) { //절댓값을 구하는 함수
  a=(a<0)?-1*a:a;
  return a;
}

int main() {
  int n,m,d;
  int sum=0;
  scanf("%d %d", &n,&m);
  scanf("%d", &d);
  int arr[405][405];
    
  for (int i=1;i<=n;i++) { //왼쪽 위 모서리와의 택시 거리가 D 미만인 칸들을 1로 설정
    for (int j=1;j<=m;j++) {
      if (abs(1-i)+abs(1-j) < d) {
        arr[i][j]=1;
      }
    }
  }
    
  for (int i=1;i<=n;i++) { //오른쪽 위 모서리와의 택시 거리가 D 미만이고 1로 설정된 칸들을 2로 설정
    for (int j=1;j<=m;j++) {
      if (abs(n-i)+abs(1-j) < d&&arr[i][j]==1) {
        arr[i][j]=2;
      }
    }
  }
    
  for (int i=1;i<=n;i++) { //왼쪽 아래 모서리와의 택시 거리가 D 미만이고 2로 설정된 칸들을 3으로 설정
    for (int j=1;j<=m;j++) {
      if (abs(1-i)+abs(m-j) < d&&arr[i][j]==2) {
        arr[i][j]=3;
      }
    }
  }
    
  for (int i=1;i<=n;i++) { //오른쪽 아래 모서리와의 택시 거리가 D 미만이고 3으로 설정된 칸들의 개수를 센다
    for (int j=1;j<=m;j++) {
      if (abs(n-i)+abs(m-j) < d&&arr[i][j]==3) {
        sum++;
      }
    }
  }
    
  printf("%d",sum);
}

4개의 모서리와의 거리가 모두 D 미만인 칸의 개수를 세는 코드이다.

---

# 맞는데 왜 틀림?

이 문제에서 맞는데 왜 틀렸는지 의문이 들 경우, 다음의 사항을 확인해보자.
 
- 택시 거리를 구하는 과정이 잘못되었다.
- 4개의 모서리의 경우를 각각 검사하지 않고, 하나의 모서리를 4번 검사하는 등의 실수가 있다.

---

# 정리

★★★★☆
애드 혹 문제답지 않게 풀이가 다양하게 나올 수 있는 점이 마음에 들었다. 복잡한 테크닉을 사용하기보단 문제를 이해하고, 그것을 어떻게 구현할지를 고민하는 것에 충실해야 하는 문제.