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

이번에는 BOJ의 17370번 "육각형 우리속의 개미" 문제를 풀어보도록 하자

여기에서 눈여겨 봐야 할 점은

• 처음에 이동은 편의상 반드시 북쪽(위쪽)으로 이동한다
• 개미가 변이 세갈레인 점에 도착하면, 자신이 이동해온 변을 제외한 나머지 두 변 중 하나를 골라 그 방향으로 회전
• 입력으로 주어지는 정수 N의 크기가 (1 <= N <= 22)

이렇게 3가지이다. 이것에 유의해서 이동하는 경로에 가중치를 넣어서 각점을 유니크한 값으로 만들어 준다. 가중치는 각 북쪽(위쪽) 경로를 기준으로 시계 방향으로 [23, 1, 1, -23, -1, -1] 로 해주었고, 이를 통해 답을 구하기 위해서 boolean 배열을 chk로 지정해주고, 총 크기를 2001(임의의 값, 반드시 23 * 22 * 2 보다는 크게 해줬다.)로 해준다. 맨처음 위치를 1000으로 하면, chk[1000]을 true로 해주고 위치 1000부터 시작해서 맨처음 북쪽(위쪽)으로 이동 하기 때문에, 위치가 1023 점을 지나게 되니, 먼저 현재 방향회전을 한 횟수 cnt 가 0인지 아닌지 판단해주고, 그다음에 chk[1023]이 true인지 false 인지 판단 해주고, 다음 방향회전을 진행하게 해주면 된다.

성공한 코드는 아래와 같다.

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

public class sample {
    static boolean[] chk = new boolean[2001];
    static int[] weight = { 23, 1, 1, -23, -1, -1 };
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        chk[1000] = true;
        bw.write(calc(N, 1000 + weight[0], 0) + "\n");

        bw.flush();
        br.close();
        bw.close();
    }

    static int calc(int cnt, int cur, int w) {
        if (cnt == 0) {
            if (chk[cur])
                return 1;
            else
                return 0;
        }
        if (chk[cur])
            return 0;

        chk[cur] = true;
        int temp = calc(cnt - 1, cur + weight[(w + 5) % 6], (w + 5) % 6)
                + calc(cnt - 1, cur + weight[(w + 1) % 6], (w + 1) % 6);
        chk[cur] = false;
        return temp;
    }
}

 

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

17370번: 육각형 우리 속의 개미