유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.
파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.
파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.
파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.
파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.
아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.
설명
DSF를 통해 풀었다.
파이프가 차지하는 좌표를 관리하기 위해 pipe라는 클래스를 따로 만들었다.
파이프의 방향에 따라 다음으로 이동가능한 →, ↘, ↓ 방향을 boolean 배열을 통해 표시했다. 벽에 닿지 않으면서 이동가능한 좌표면 파이프를 이동시켰다.
파이프의 좌표가 N,N에 닿으면 count를 추가했다. DSF를 다 돌고 나온 count의 값이 정답이다.
코드
//17070번 파이프 옮기기 1.java
package boj20211229;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 파이프_옮기기1_17070 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int count;
static class point{
int i;
int j;
point(int i, int j){
this.i=i;
this.j=j;
}
@Override
public String toString() {
return "point [i=" + i + ", j=" + j + "]";
}
}
static class pipe{
point head;
point tail;
pipe(point head, point tail){
this.head=head;
this.tail=tail;
}
@Override
public String toString() {
return "pipe [head=" + head + ", tail=" + tail + "]";
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
int N = Integer.parseInt(br.readLine());
int[][] house = new int[N+1][N+1];
for(int i=1;i<=N;i++) {
st = new StringTokenizer(br.readLine()," ");
for(int j=1;j<=N;j++) {
house[i][j] = Integer.parseInt(st.nextToken());
}
}
count=0;
solution(new pipe(new point(1, 2), new point(1, 1)), N, house);
System.out.println(count);
}
static void solution(pipe pipe, int N, int[][] house) {
if(pipe.head.i==N && pipe.head.j==N) {
count++;
return;
}
int[] di = {0,1,1};
int[] dj = {1,0,1};
boolean[] check = new boolean[3];
if(pipe.head.i == pipe.tail.i)check[0]=true;
if(pipe.head.j == pipe.tail.j)check[1]=true;
if(pipe.head.i-pipe.tail.i==1 && pipe.head.j-pipe.tail.j==1) {
check[0]=true;
check[1]=true;
}
check[2]=true;
for(int d=0;d<3;d++) {
if(!check[d])continue;
int i = pipe.head.i+di[d];
int j = pipe.head.j+dj[d];
if(1<=i&&i<=N&&1<=j&&j<=N) {
if(d==2) {
if(house[i-1][j]==1 || house[i][j-1]==1) {
break;
}
}
if(house[i][j]==0) {
solution(new pipe(new point(i, j), pipe.head), N, house);
}
}
}
}
}
