BOJ 3234 - LUKA

문제

BOJ 3234 - LUKA

루카(LUKA)는 2D 격자에서 원점 (0, 0)에서 시작하여 이동한다. 목표 위치 (X, Y)가 주어지고 K번의 이동 명령이 주어진다.

이동 명령은 다음과 같다:

• I: x 증가 (동쪽)
• S: y 증가 (북쪽)
• Z: x 감소 (서쪽)
• W: y 감소 (남쪽)

루카의 현재 위치와 목표 위치 (X, Y)가 인접(8방향 + 자기 자신)한 관계가 되는 최초 이동 횟수 k를 출력한다. K번 이동 후에도 조건을 만족하지 못하면 -1을 출력한다.

입력

• 첫 번째 줄에 목표 위치 X, Y와 이동 횟수 K가 주어진다.
• 두 번째 줄에 K개의 이동 명령 문자(I, S, Z, W)가 주어진다.

출력

목표 위치에 인접한 최초 이동 횟수를 출력한다. 조건을 만족하지 못하면 -1을 출력한다.

예제

풀이

루카의 위치를 이동 명령에 따라 갱신하면서, 매 이동 후 목표와의 인접 여부를 확인하는 시뮬레이션 문제이다.

1. 목표 위치 (X, Y)와 이동 횟수 K를 입력받는다.
2. 시작 위치 (0, 0)에서 목표와의 인접 여부를 먼저 확인한다 (k=0).
3. K번의 이동 명령을 순서대로 처리하며 루카의 위치를 갱신한다.
4. 매 이동 후 현재 위치와 목표 위치의 체비쇼프 거리(8방향 포함)가 1 이하인지 확인한다.
5. 조건을 만족하는 최초 k를 출력하고 종료한다. K번 후에도 미충족이면 -1을 출력한다.

핵심 아이디어: 인접 조건을 dx, dy 배열로 9가지 방향(자기 자신 포함)을 미리 정의하여 간단히 검사한다. 최초로 조건을 만족하는 시점을 찾으므로, 조건 만족 즉시 출력 후 printed 플래그를 설정한다.

코드

#include <iostream>
using namespace std;
 
int X, Y, x, y;
int K;
bool printed;
 
int dx[9] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
int dy[9] = {0, 1, 0, -1, -1, -1, 0, 1, 1};
 
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
 
  cin >> X >> Y >> K;
  for (int i = 0; i < 9; i++)
  {
    if (x + dx[i] == X && y + dy[i] == Y)
    {
      cout << 0 << '\n';
      printed = 1;
    }
  }
 
  for (int k = 1; k <= K; k++)
  {
    char c;
    cin >> c;
    if (c == 'I')
      x++;
    else if (c == 'S')
      y++;
    else if (c == 'Z')
      x--;
    else
      y--;
 
    for (int i = 0; i < 9; i++)
    {
      if (x + dx[i] == X && y + dy[i] == Y)
      {
        cout << k << '\n';
        printed = 1;
      }
    }
  }
 
  if (!printed)
    cout << -1;
}

복잡도

• 시간: O(K) - K번의 이동 명령을 순서대로 처리
• 공간: O(1) - 고정 크기의 방향 배열만 사용