106. 육각형 우리 속의 개미 (백준 17370)

문제

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

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

문제

무한히 많은 정육각형이 서로 맞닿아 놓인 형태의 개미 우리가 있다. 다음 그림과 같은 형태이고, 하얀색 변으로만 개미가 다닐 수 있다.

곤충 관찰이 취미인 유이는 세 정육각형이 서로 맞닿아 있는 어떤 점 위에 개미를 하나 올렸다. 이렇게 우리에 올라온 개미는 그 자신에게 미지의 영역인 우리를 페로몬을 뿌리며 탐색하기 시작했다. 처음 개미는 점과 연결된 세 변 중 하나를 향해 이동을 시작하는데, 편의를 위해 이 첫 번째 이동이 북쪽을 향하도록 돌려서 보자.

만약 개미가 변이 세 갈래로 갈라지는 점에 도착하면, 자신이 이동해온 변을 제외한 나머지 두 변 중 하나를 골라 그 방향으로 회전하여 탐색을 계속한다.

연두색은 시작 지점, 초록색은 개미가 탐색하며 페로몬을 뿌린 경로. 검은색은 개미, 주황색은 다음 이동을 위해 선택 가능한 두 변을 나타낸다.

개미가 이전에 방문했던, 즉, 페로몬이 뿌려진 지점에 도착하면 이곳이 이미 익숙한 영역이라는 착각에 빠지고 더 이상의 탐색을 멈춘다. 이렇게 탐색을 멈췄을 때, 방향을 회전한 횟수가 정확히 N번이 되는 경우의 수를 구해보자.

방향을 7번 회전하는 두 경로. 페로몬의 궤적은 동일해도 개미의 이동 방향에 따라 경로를 구별하도록 한다.

입력

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

출력

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

 

풀이

일단 육각형과 움직임을 어떻게 구현해야할 지 생각해야 한다.

우선 좌표상으론 각각의 방향에 따라 아래 사진과 같이 6가지 움직임으로 구현할 수 있다.

그리고, 각각의 움직임은 그 다음 동작으로 2가지의 방향밖에 선택할 수 없다.

처음에는 최종적으로 방향이 겹치지 않는지만 검사하였는데, 그러면 예제에서 오류가 발생한다.

왜나하면 문제는 경로를 구별할 때, 위 움직임대로 고려하지 않기 때문이다.

사진의 오른쪽처럼, 아래로 내려가다 왼쪽으로 꺾은 경우 (0->1) 이 움직임을 회전시켰을때 동일한 액션을 취하는 움직임을 다 같은 경우로 보는 것이다.

따라서 다음에 가능한 움직임 + 이 방향 전환이 어떤 타입에 속하는지를 매핑해서 계산해야한다.

또한 방향 이동이 N번이므로, 실제 움직임은 N+1번이고, 방문한 점은 N+2개이다.

경로를 묻는 문제이므로, 시작점과 맨 첫 움직임은 중요하지 않다.

어차피 다른 시작점에서 다른 방향으로 시작해도 돌리면 똑같기 때문.

그래도 22번 움직일 수 있기 때문에 넉넉하게 51X51으로 배열을 선언해서, 가운데에서 3번 방향(올라가며) 시작하게 했다.

개미의 움직임만 파악하면 문제를 푸는 것은 간단하다.

1. 방문한 노드인지 파악
2. 만약 방문한 노드면, N번 방향전환을 했는지 파악 -> 맞으면 정답
3. 방문도 안한 노든데 N번 방향전환을 했으면 X
4. 다음 경로로의 탐색은 위 경로매핑을 통해 이동

N의 최대가 22이기 때문에, 최대 22 깊이이므로 재귀를 사용하여 구현할 수 있다.

 

코드

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

public class Main {

    //방향회전 수
    static int N;
    //50,50에서 시작
    static boolean[][] map = new boolean[51][51];

    static int[] moveX = {0,-1,1,0,-1,1};
    static int[] moveY = {1,1,1,-1,-1,-1};
    //방향회전 -> 점 방문
    static int[][] availableMove = {{2,1},{0,4},{5,0},{4,5},{1,3},{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());
        map[25][25] = true;
        seeking(0,3,25,24);
        System.out.println(answer);
    }

    public static void seeking(int count, int pastMove, int x, int y){
        if(map[y][x]){
            if(count == N){
                answer++;
            }
            return;
        }
        if(count == N) return;
        map[y][x] = true;
        for(int i=0; i<2; i++){
            seeking(count+1, availableMove[pastMove][i], x+moveX[availableMove[pastMove][i]], y+moveY[availableMove[pastMove][i]]);
        }
        map[y][x] = false;
    }

}

결과