/ BOJ

BOJ_17070_파이프옮기기_JAVA

문제 : 파이프 옮기기

링크 : BOJ_17070_파이프옮기기

접근 방식

되게 오랜만에 푸는 것만 같은 탐색 문제이다. 나는 dfs에 조건을 적용하여 풀이했다.

파이프는 2칸을 차지한다고 말했지만, 사실상 처음 시작위치의 오른쪽 점을 시작위치로 잡은 DFS와 똑같았다.

파이프가 움직이는 조건은 다음과 같다.

  1. 파이프는 움직이면서 회전하는데, 한 번에 90도 회전할 수 없다. - 파이프는 왼쪽, 왼쪽 아래 대각선, 아래로만 움직이는데, 왼쪽에서 아래쪽으로 또는 아래쪽에서 왼쪽으로 한 번에 회전하지 못하고, 대각선을 거쳐야지만 회전할 수 있다.

  2. 파이프는 이동하려는 방향이 비어있어야만 이동할 수 있다. 하지만, 대각선의 경우 대각선 위치에 겹치는 왼쪽과 아래쪽도 비어있어야 움직일 수 있다.

DFS를 구현하여 위 조건에 맞게 재귀를 호출시켜준 후, 시작점에서 목적 위치에 도달할 때마다 카운트를 1 증가시켜주면, 해당 탐색에서 파이프를 목적지까지 이동시킬 수 있는 총 경우의 수를 알 수 있게 된다.

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_17070_파이프옮기기 {

	static int N, arr[][];
	static int[][] dir = { { 0, 1 }, { 1, 1 }, { 1, 0 } };
	// A는 가로, B는 세로, C는 대각선
	static final int A = 9, B = 8, C = 7;
	static int ans;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(in.readLine());
		arr = new int[N][N];
		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		arr[0][1] = A;
		dfs(0, 1, arr);

		System.out.println(ans);
	}

	public static void dfs(int x, int y, int[][] arr) {

		if (x == N - 1 && y == N - 1) {
			ans++;
			return;
		}

		for (int d = 0; d < 3; d++) {
			int dx = x + dir[d][0];
			int dy = y + dir[d][1];
			if (dx >= 0 && dx < N && dy >= 0 && dy < N) {
				// 오른쪽으로 이동할 수 있을 때
				if (d == 0 && (arr[x][y] == A || arr[x][y] == C) && arr[dx][dy] == 0) {
					int temp = arr[x][y];
					arr[x][y] = 0;
					arr[dx][dy] = A;
					dfs(dx, dy, arr);
					arr[dx][dy] = 0;
					arr[x][y] = temp;
				}
				// 아래로 이동할 수 있을 때
				if (d == 2 && (arr[x][y] == C || arr[x][y] == B) && arr[dx][dy] == 0) {
					int temp = arr[x][y];
					arr[x][y] = 0;
					arr[dx][dy] = B;
					dfs(dx, dy, arr);
					arr[dx][dy] = 0;
					arr[x][y] = temp;
				}
				// 대각선으로 이동할 수 있을 때
				if (d == 1 && arr[dx][dy] == 0 && arr[dx][dy - 1] == 0 && arr[dx - 1][dy] == 0) {
					int temp = arr[x][y];
					arr[x][y] = 0;
					arr[dx][dy] = C;
					dfs(dx, dy, arr);
					arr[dx][dy] = 0;
					arr[x][y] = temp;

				}
			}

		}

	}

}