기사의 현명한 아내: 불가능한 여정 찾기(java 코드포함 풀이)

문제 정보

데블스플랜2 기사의 여정, 근데 코딩테스트 곁들인..

 

문제 풀이

저는 이런 종류의 문제를 한번에 못짜기 때문에 분할정복(?) 하는 편 입니다.

그래야 잘못된 길로가도 코드 몇 라인 정도는 살려서 써먹을 수 있더라고요

 

1. 기사의 이동 구현하기

• 8 방향 이동을 배열로 정의
• 이동 가능한 위치인지 확인(이전에 갔던 곳이거나 맵의 밖이면 못가도록 처리)

int[] dx = {2, 1, -1, -2, -2, -1, 1, 2};
int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};

private boolean isValid(int x, int y, int n, boolean[][] visited) {
    return x >= 0 && x < n && y >= 0 && y < n && !visited[x][y];
}

 

2. 백트래킹 구현하기

• 모든 칸에 방문하면 결과값 true; 반환
• 방문 한 칸 visited[x][y]에 true 체크
• 잘못된 길이면 visited[x][y]에 체크한 true 빼고 다시 찾기
• 루프가 끝났는데 모든 칸에 방문을 못하면 결과값 false; 반환

private boolean knightTour(int x, int y, int moveCount, int n, boolean[][] visited) {
    if (moveCount == n * n) return true;

    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (isValid(nx, ny, n, visited)) {
            visited[nx][ny] = true;
            if (knightTour(nx, ny, moveCount + 1, n, visited)) return true;
            visited[nx][ny] = false; // 백트래킹
        }
    }

    return false;
}

 

3. 시작 좌표값들 루프로 굴리기

• 주어진 시작 좌표들 각각에 대해 DFS 시도
• 결과 boolean[] 반환

public boolean[] knightTour(int n, int[][] positions) {
    boolean[] result = new boolean[positions.length];

    for (int idx = 0; idx < positions.length; idx++) {
        int startX = positions[idx][0];
        int startY = positions[idx][1];
        boolean[][] visited = new boolean[n][n];
        visited[startX][startY] = true;

        result[idx] = knightTour(startX, startY, 1, n, visited);
    }

    return result;
}

 

4. 최적화 하기

• 항상 성공하는 케이스 true 배열로 스킵
• 항상 실패하는 케이스 false 배열로 스킵
• n = 5일 때만, 백트래킹 수행하기

public boolean[] knightTour(int n, int[][] positions) {
    boolean[] result = new boolean[positions.length];

    // 실패 보드
    if (n == 2 || n == 3 || n == 4) {
        Arrays.fill(result, false);
        return result;
    }

    // 항상 성공 보드
    if (n == 1 || n >= 6) {
        Arrays.fill(result, true);
        return result;
    }

    // n == 5인 경우만 백트래킹
    for (int idx = 0; idx < positions.length; idx++) {
        int startX = positions[idx][0];
        int startY = positions[idx][1];
        boolean[][] visited = new boolean[n][n];
        visited[startX][startY] = true;

        result[idx] = knightTour(startX, startY, 1, n, visited);
    }

    return result;
}

 

테스트

1. 최솟값 테스트 : 출발과 동시에 전 칸을 방문할 수 있다

입력

n = 1
positions = [[0, 0]]

 

결과

[true]

 

2. 완주 불가능한 보드판 테스트 : 3x3은 어디서든 모두 방문 할 수 없다 (2x2, 4x4 마찬가지)

입력

n = 3
positions = [[0, 0], [1, 1], [2, 2]]

결과

[false, false, false]

 

3. 성공 실패가 나눠지는 보드판 테스트 : 5x5는 한정된 완주 시작 위치가 정해져있다

입력

n = 5
positions = [[0, 0], [0, 1], [3, 4], [4, 3], [2, 2]]

결과

[true, false, false, false, true]

 

4. 항상 완주 가능한 보드판 테스트 : 6x6 이상은 모두 완주 가능하다

입력

n = 6
positions = [[0, 0], [1, 1], [3, 3], [4, 2], [5, 5]]

결과

[true, true, true, true, true]

 

실행코드

public class KnightToursPlan {

    public static void main(String[] args) {
        // 예제 4가지 테스트
        runTest(1, new int[][]{{0, 0}});
        runTest(3, new int[][]{{0, 0}, {1, 1}, {2, 2}});
        runTest(5, new int[][]{{0, 0}, {0, 1}, {3, 4}, {4, 3}, {2, 2}});
        runTest(6, new int[][]{{0, 0}, {1, 1}, {3, 3}, {4, 2}, {5, 5}});
    }

    public static void runTest(int n, int[][] positions) {
    	System.out.println("### start tours ============================");
        System.out.println("n = " + n);
        System.out.println("positions = " + Arrays.deepToString(positions));
        boolean[] result = knightTour(n, positions);
        System.out.println("결과 = " + Arrays.toString(result));
        System.out.println("### end tours ============================");
    }
}

 

 

회고

처음으로 문제를 만들어 봤는데, 생각보다 훨씬 어려웠다...

1시간정도 안에 대부분의 코드는 구현했는데,

실행가능한 형태를 머릿속으로 찍어보려니 OOM 발생해서 앞에 어딜 갔는지 까먹게되었다.

메모장에 써가면서 좌표를 찍어도 한 눈에 안들어오니까 어려워서 엑셀에다가 하나씩 색칠하면서 했는데,

이 과정이 상당히 도움되었다.

휴리스틱이라는것도 있다는데 다음에 도전해봐야겠다

결국 3시간 걸리고 글쓰는데 1시간 쓰니까 노곤노곤한게 잠이 참 잘오겠다