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

문제 링크

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

문제

티어: 골드 3
알고리즘: 백트래킹, 그래프

입력

첫 번째 줄에 하나의 정수 N(1 ≤ N ≤ 22)이 주어진다.

출력

첫 번째 줄에 개미가 방향 회전을 N번 하고 멈추는 경우의 수를 출력한다.

풀이

회전을 N번하고 멈추는 경우의 수를 출력해야 한다.

N이 22로 작기 때문에 모든 경우의 수를 살펴볼만 하다. (완탐)

그래서 육각형에서 개미가 갈 수 있는 곳을 좌표로 나타내는 2차원 배열을 만든다.
이 배열을 만드는 것은 어렵지 않다.

상대적으로 점이 위에 있으면 y좌표로 -1이고, 점이 왼쪽에 있으면 x 좌표로 -1이라 생각하고 만들면 된다.

그래서 나는 다음과 같은 맵을 만들었다.
boolean[][] map = new boolean[49][49]; //중간 위치 24, 24

그리고 중간 위치부터 백트래킹을 시작한다.

그런데 주의할 점이 있다.

궤적이 동일하다고 했을 때 이동 방향 또한 같다면 같은 경우의 수로 봐야한다.

그래서 처음 위치에서 아래 방향으로 가는 경우는 세주지 않는다. 왜냐하면 위로 간 궤적을 회전했을 때 결국 같기 때문이다.

이 풀이의 연산은 최대 2^22을 넘지 않는다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static final int[][] nextD = {{2, 3}, {4, 5}, {0, 4}, {0, 5}, {1, 2}, {1, 3}};
    static final int[] dx = {0, 0, 1, -1, 1, -1};
    static final int[] dy = {-1, 1, -1, -1, 1, 1};
    static int N;
    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());
      
      boolean[][] map = new boolean[49][49]; //중간 위치 24, 24
      map[24][24] = true;
      dfs(0, 0, 24, 23, map);
      System.out.println(answer);
  }
  
  static void dfs(int cnt, int beforeD, int curX, int curY, boolean[][] map) {
      if(map[curY][curX]) {
          if(cnt == N) {
              answer += 1;
          }
          return;
      }
      if(cnt == N) {
          return;
      }
      map[curY][curX] = true;
      for(int i=0; i<2; i++) {
          int di = nextD[beforeD][i];
          int nx = curX + dx[di];
          int ny = curY + dy[di];
          dfs(cnt + 1, di, nx, ny, map);
      }
      map[curY][curX] = false;
  }
}