2564 경비원

2564 경비원 / c++ / Silver1 / 54분

문제 및 코드

풀이 과정

구현

1. 동근이의 위치 X로부터 각 상점까지의 최단 거리의 합을 구하는 문제
2. 단, 블록을 가로질러 갈 수 는 없고 각 면을 타고 가야한다.
3. 여기서 나올 수 있는 분기는 총 3가지이다.
   1. 같은 측면에 있는 상점
   2. 인접한 옆 측면에 있는 상점
   3. 맞은편 측면에 있는 상점
4. 거리를 구하기 위해 측면의 번호와, 상점의 위치 측정 기준이 불편해서 재가공했다. (정보의 재가공)
   1. 우선 측면 번호의 경우, 기존엔 북 1, 남 2, 서 3, 동 4 였다. 하지만 이러면 시계방향 진행인지, 맞은 편인지를 측정하기가 불편했다.
   2. 그래서 바꾼게, 북 0, 동 1, 남 2, 서 3 으로 바꿨다. 이러면 시계방향은 1증가, 반시계 방향은 1감소, 맞은편은 절대값으로 2차이로 파악할 수 있기 때문에 훨씬 편하다.
   3. 마찬가지로 상점 위치의 기준점도, 기존에는 남, 북은 왼쪽 기준, 동, 서는 위쪽 기준으로 위치를 측정했다.
   4. 이를 북과 동은 기존대로 두고, 남은 오른쪽 기준, 서는 아랫쪽 기준으로 위치를 재가공 했다. (시계방향으로 진행했을 때의 원점 기준)
5. 위와 같이 정보의 재가공을 하고 나면 아래와 같이 식으로 길이를 계산할 수 있다.
   1. 측면의 차이 = (StartSide - TargetSide + 4) % 4
      • 0 은 같은 측면
      • 1 은 시계 방향
      • 2 는 맞은 편
      • 3 은 반 시계 방향
   2. 해당 상점까지의 길이는 다음과 같이 구할 수 있다.
      • 같은 측면 = 절대값(시작 위치와 상점 위치의 차이)
      • 시계 방향 = (시작 측면의 길이 - 시작 위치) + 상점의 위치
      • 반 시계 방향 = 시작 위치 + (상점 측면의 길이 - 상점의 위치)
      • 맞은 편 = 작은값(시계 방향, 반시계 방향) + 인접한 면의 길이
        (여기서 시계 방향으로 지나가든, 반 시계 방향으로 지나가든 인접한 면은 무조건 한 번 지나가야 함)
6. 위와 같은 공식으로 최소 길이를 구한 뒤, 그 값들을 모두 더해서 출력
7. 해결

다시 생각해 볼 점

1. 바로 어제 풀어던 문제(봄버맨)에서 정보의 재가공의 중요성을 크게 깨닫고, 여기서 충분히 활용할 수 있는 문제였다.
2. 있는 그대로의 정보로는 시계방향, 반시계 방향을 구할 때 분기가 너무 많아지게 된다. (시작위치가 어느 측면이냐에 따라서)
3. 하지만 위와 같이 계산하기 편한 값으로 미리 설정해두고 나니 계산이 일목요연해졌고, 편하게 결과값을 구할 수 있었다.
4. 문제 분석부터 정보의 재가공까지 시간이 좀 걸렸지만, 결국 한번의 시도로 바로 정답을 맞힐 수 있어서 뿌듯했다. 이렇게 분석에 충분한 시간을 두는 습관을 들여야겠다.