BOJ - 17370

BOJ - 17370

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

UCPC 2021을 준비하면서, 2019 UCPC I번 문제를 풀었음.

문제 해결 방법

1. 먼저 육각형을 윗부분과 아랫부분을 찌그려뜨리면 양쪽으로 긴 직사각형 모양으로 만들 수 있음. 이때 개미가 움직인 곳을 visited[][] 배열로 확인할 수 있음.
2. N의 제한이 22이므로 2^22을 해도 TLE가 나지 않으므로 dfs를 수행.
3. dfs를 시행하는 동안 nextState는 (state + 1) % 6, (6 + state - 1) % 6으로 설정한다.
4. dfs 시행 종료 조건은 count가 N과 같을 때이며, 각 단계마다 nextState에 해당하는 x, y값의 visited가 true이며 count가 N - 1일 경우 answer를 증가시킨다.

코드

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

public class Main {
	public static int N;
	public static long answer = 0;
	public static int[] dx = {0, -1, -1, 0, 1, 1};
	public static int[] dy = {1, 0, 0, -1, 0, 0};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		solve(-1, 25, 25, 0, new boolean[50][50], "");
		
		System.out.println(answer);
	}
	
	public static void solve(int count, int x, int y, int state, boolean[][] visited, String str) {
		if(count == -1) {
			visited[x][y] = true;
			visited[x + dx[0]][y + dy[0]] = true;
			solve(0, x + dx[0], y + dy[0], 0, visited, "");
		}
		else if(count == N) {
			return;
		}
		else {
			// i - 1 % 6
			int nextState = (6 + state - 1) % 6;
			
			if(visited[x + dx[nextState]][y + dy[nextState]]) {
				if(count == N - 1) answer++;
			}
			else {
				visited[x + dx[nextState]][y + dy[nextState]] = true;
				solve(count + 1, x + dx[nextState], y + dy[nextState], nextState, visited, str + nextState);
				visited[x + dx[nextState]][y + dy[nextState]] = false;
			}
			
			// i + 1 % 6
			nextState = (state + 1) % 6;
			
			if(visited[x + dx[nextState]][y + dy[nextState]]) {
				if(count == N - 1) answer++;
			}
			else {
				visited[x + dx[nextState]][y + dy[nextState]] = true;
				solve(count + 1, x + dx[nextState], y + dy[nextState], nextState, visited, str + nextState);
				visited[x + dx[nextState]][y + dy[nextState]] = false;
			}
		}
	}

}

후기

중간에 answer를 증가시키고 return을 하는 실수가 있어 제출 3번 만에 맞았다.
처음에 육각형으로 만드는 아이디어가 굉장히 힘들었음. 그 이후에는 단순한 dfs 문제로 풀 수 있었음.