[백준] 육각형 우리 속의 개미 - Java 17370

`완전 탐색` 문제인데 문제가 조금 신선하다.

 

맨 처음 이거 뭐 범위도 지정되어 있지 않아서, 어떻게 풀어야 하나 난감했는데

이걸 좌표로 생각해서 접근하면 결국 N <= 22이므로,

50으로 잡은 다음 중간부터 시작해야겠다고 생각이 되어 그대로 풀었다.

 

그 부분이 확실하지 않은 미지의 영역 느낌이라 좀 무서웠지만,

그렇게 놓고 진행하니까 생각보다 쉽게 풀렸다.

 

6방향으로 진행이 가능하며 해당 방향으로 진행했을 때 다음 방향은 2개로 좁혀지므로,

방향에 따른 진행방향을 `DFS`로 접근하여 풀었다.

 

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

public class Main {
    static boolean[][] grid = new boolean[50][50];
    static int N;
    static int[] dy = {-1, -1, -1, 1, 1, 1};
    static int[] dx = {0, -1, 1, 0, -1, 1};
    static int[][] nextMove = {{1, 2}, {0, 4}, {0, 5}, {4, 5}, {3, 1}, {3, 2}};
    static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        grid[25][25] = true;

        dfs(0, 0, 24, 25);

        System.out.println(answer);
    }

    public static void dfs(int count, int prevIdx, int y, int x){
//        if(grid[y][x]){
//            if(count == N){
//                answer++;
//            }
//
//            return;
//        }

        if(count == N){
            if(grid[y][x]){
                answer++;
            }

            return;
        }

        if(grid[y][x]){
            return;
        }

        grid[y][x] = true;

        for(int i = 0; i < 2; i++){
            dfs(count + 1, nextMove[prevIdx][i], y + dy[nextMove[prevIdx][i]], x + dx[nextMove[prevIdx][i]]);
        }

        grid[y][x] = false;
    }
}