[백준] 17070번 - 파이프 옮기기 1

문제 >

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.

오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.

 

 

파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

 

 

파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.

 

가로

 

세로

 

대각선

 

가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

 

입력 >

첫째 줄에 집의 크기 N(3 ≤ N ≤ 16)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.

 

출력 >

첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.

 

해결방법 > 

DFS(깊이우선탐색) 해결할 수 있는 문제이다.

 

파이프가 놓여있는 방향에 따라 이동할 수 있는 경우의 수가 달라진다.

 

1. 가로로 놓여있을 경우 :

가로 - 끝점을 기준으로 오른쪽 원소값이 0이거나 배열의 인덱스를 벗어나지 않을 때

대각선 - 끝점을 기준으로 오른쪽, 아래쪽, 대각선 원소값이 0이거나 배열의 인덱스를 벗어나지 않을 때 

 

2. 세로로 놓여있을 경우 :

세로 - 끝점을 기준으로 아래쪽 원소값이 0이거나 배열의 인덱스를 벗어나지 않을 때

대각선 - 끝점을 기준으로 오른쪽, 아래쪽, 대각선 원소값이 0이거나 배열의 인덱스를 벗어나지 않을 때 

 

3. 대각선으로 놓여있을 경우 :

가로 - 끝점을 기준으로 오른쪽 원소값이 0이거나 배열의 인덱스를 벗어나지 않을 때

세로 - 끝점을 기준으로 아래쪽 원소값이 0이거나 배열의 인덱스를 벗어나지 않을 때

대각선 - 끝점을 기준으로 오른쪽, 아래쪽, 대각선 원소값이 0이거나 배열의 인덱스를 벗어나지 않을 때 

 

각 방향에서 가능한 경우를 모든 탐색한다.

 

[JAVA]

package baekjoon;

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

public class BOJ_17070 {
	static int[] dx = {0, 1, 1};
	static int[] dy = {1, 0, 1};
	static int cnt = 0;
	static int n;
	static int[][] map;
	
	public static boolean possible(int x, int y, int d) {
		int nx = x + dx[d];
		int ny = y + dy[d];
		if(d == 0 || d == 1) {
			if(nx >= 0 && ny >= 0 && nx < n && ny < n && map[nx][ny] == 0) return true;
		}
		else {
			if(nx >= 0 && ny >= 0 && nx < n && ny < n) {
				if(map[nx - 1][ny] == 0 && map[nx][ny - 1] == 0 && map[nx][ny] == 0) return true;
			}
		}
		return false;
	}
	
	public static void dfs(int x, int y, int d) {
		int nx = x + dx[d];
		int ny = y + dy[d];
		if(nx == n-1 && ny == n-1) {
			cnt++;
			return;
		}
		
		if(d == 0) {
			if(possible(nx, ny, 0)) dfs(nx, ny, 0);
			if(possible(nx, ny, 2)) dfs(nx, ny, 2);
		}
		else if(d == 1) {
			if(possible(nx, ny, 1)) dfs(nx, ny, 1);
			if(possible(nx, ny, 2)) dfs(nx, ny, 2);
		}
		else {
			if(possible(nx, ny, 0)) dfs(nx, ny, 0);
			if(possible(nx, ny, 1)) dfs(nx, ny, 1);
			if(possible(nx, ny, 2)) dfs(nx, ny, 2);
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk = new StringTokenizer(br.readLine());
		n = Integer.parseInt(tk.nextToken());
		map = new int[n][n];
		for(int i = 0; i < n; i++) {
			tk = new StringTokenizer(br.readLine());
			for(int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(tk.nextToken());
			}
		}
		dfs(0, 0, 0);
		System.out.println(cnt);
	}
}