[Java] 백준 16948 데스 나이트 - 실버1

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

16948번: 데스 나이트

 

 

bfs를 쓰면 시간이 너무 오래걸릴 것 같아 수식으로 해결해봤다.

규칙을 찾는 데 시간이 좀 걸렸지만, 수식을 사용하기 때문에 수행시간이 빠르다. 

 

 

 

 

 

1. 갈 수 없는 곳 판별하기

• 이렇게 표로 슥슥 그려보면 갈 수 없는 지점이 보인다
• 행(row)은 시작지점의 2의 배수만큼 떨어져 있어야하고
• 열(col)은
  • 시작지점과 (2 x 홀수)만큼 차이가 나면 (시작열 + 1)의 2의 배수만큼 떨어져있어야하고 -- (a)
  • (2 x 짝수)만큼 차이가 나면  2의 배수만큼 떨어져있어야한다  -- (b)
• 이 표를 기반으로 갈 수 있는 위치인지 아닌지 판별하는 식을 작성한다

 

 

 2. 이동하는 최소 거리 수식으로 계산하기

• 떨어진 거리는 그림과 같이 계산한다
• 윗방향으로 가는 거리를 계산한 후, 옆 방향으로 가는 거리를 계산해준다
• 윗 방향으로 가는 거리 = 세로길이/2   -- (c)
• 옆 방향으로 가는 거리 = (가로길이 - 세로길이/2) /2    -- (d)

 

이 방법을 사용하면 예외없이 답이 잘 나온다.

(하나하나 테스트 해본 결과임)

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws IOException {
  	//입력받기
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    br.readLine();
    StringTokenizer st = new StringTokenizer(br.readLine());
    int r1 = Integer.parseInt(st.nextToken());
    int c1 = Integer.parseInt(st.nextToken());
    int r2 = Integer.parseInt(st.nextToken());
    int c2 = Integer.parseInt(st.nextToken());
    
    int result = -1;
    boolean isValid = true;

    //갈 수 없는 행인지 확인
    if (Math.abs(r1-r2) % 2 !=0) {
      System.out.println(-1);
      return;
    }

    //갈 수 없는 열인지 확인
    int k = Math.abs(r1-r2)/2;
    if (k %2 != 0 && Math.abs(c1+1-c2)%2 != 0) //2의 홀수배일 때(a)
        isValid = false;

    if (k %2 == 0 && Math.abs(c1-c2) % 2 != 0) //2의 짝수배일 때(b)
        isValid = false;

    //계산
    if (isValid) {
      //행으로 움직이는 것 먼저 계산(c)
      int rowMove = 0;
      if (r1 - r2 != 0)
        rowMove = Math.abs(r1-r2)/2;

      //열로 움직이는 것 계산(d)
      int colMove = 0;
      int tmp = Math.abs(c1-c2)+1-rowMove;
      if (tmp > 0)
        colMove = tmp/2;

      result = rowMove + colMove;
    }

    System.out.println(result);
  }
}

• 코드는 윗 설명 그대로 구현했다