[백준 18137] 나이트의 경로 - JAVA

BOJ Link

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

 

개요

처음 기록하는 알고리즘 문제이다. 누군가 내 글로 해답을 찾는데 도움되게 쓰기보단, 내 사고의 흐름만 기록하는 방식으로 작성하려 한다.

 

시간제한 0.5초 구현+애드 혹 문제이다. 애드 혹이란 정해진 방법 없이 개인의 아이디어로 푸는 문제 분류이다. (알고리즘 기법 자체가 아니다.)

 

풀이 과정

1. x칸 y칸은 각각 왼쪽/아래에서 몇번 째 칸인지 의미한다. 따라서 x>0, y>0일 때만 탐색한다. 이때,

주어진 식에서 엣지 케이스 (분자가 int범위를 초과할 때) 나 익셉션이 발생할 경우 (예를 들면 division by zero)는 없다고 생각했다.

전자는 확신하려면 k=2^31 - 1일 때로 증명해야 해서 일단 가정했다.

 

2. 방문 칸에는 2^31 미만의 정수 k만 주어진다. 결과값 k는 int범위 내이나 정작 구하는데 필요한 x, y가 int범위를 벗어날 수 있다. 이걸 고려했고 이 문제에는 해당사항이 없어서 x, y를 int로 썼다.

 

3. 나이트는 한 번 방문한 칸에는 다시 갈 수 없다. 한마디로 visited 같은 경로 체크 컨테이너가 필요하다.

인덱스 기반 visited 탐색을 할 수 있는 문제이므로, array가 O(1)의 조회 성능을 가진다. 다만, 이 문제에서는 2^31개의 칸이 있기 때문에 boolean array를 쓴다면 메모리 초과가 날 것 같았다. 그래서 hashset에 기록하는 방법을 생각했다. 이는 역시 O(1)이다.

 

4-1. 나이트는 총 8칸으로 이동 가능하다. 이는 델타로 구현하며, 갈 수 있는 칸 중에 가장 적은 숫자가 적힌 칸으로 이동하고 set에 경로를 추가한다.

 

4-2. 만약, 아무 칸으로도 갈 수 없으면 (x==ax && y=ay) 현재 위치를 출력하고 종료한다. (해당 케이스가 없어서 뺐다.)

 

특이 사항

k = 2401일 때부터 나이트가 1378번 위치에서 멈춘다. 다만, assert로 k > 2401인 입력은 없음을 확인했다. 원래는 고려되어야 할 케이스라고 생각해서 케이스 추가/조건 수정 요청을 올렸다.

 

제출 코드

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    static Set<Integer> visited = new HashSet<>();
    static int cur = 1, MAX = 8, dx[] = {2, 2, -2, -2, 1, -1, -1, 1}, dy[] = {1, -1, -1, 1, 2, 2, -2, -2};

    public static void main(String[] args) {
        int N = new Scanner(System.in).nextInt();

        int x = 1, y = 1;
        visited.add(1);
        for (int i = 0; i < N; i++) {
            int[] pathInfo = findPath(x, y);
            x = pathInfo[0];
            y = pathInfo[1];
            cur = pathInfo[2];
            visited.add(cur);
        }
        System.out.println(cur);
    }

    static public int[] findPath(int x, int y) {
        int ap = Integer.MAX_VALUE;
        int ax = x;
        int ay = y;
        for (int i = 0; i < MAX; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 1 || ny < 1) continue;

            int p = getNum(nx, ny);
            if (!visited.contains(p) && p < ap) {
                ax = nx;
                ay = ny;
                ap = p;
            }
        }

        return new int[]{ax, ay, ap};
    }

    static public int getNum(int x, int y) {
        return ((x + y - 1) * (x + y - 2) / 2) + y;
    }
}