[BOJ] Q17070 파이프 옮기기1

🔗문제 링크

BOJ 17070번

🔒 문제 설명

(1,1),(1,2)에 놓여진 파이프가 있다.

파이프를 →, ↘, ↓ 방향으로만 옮겨 한쪽 끝을 NxN 격자판의 (N,N)위치로 옮겨야 한다.

파이프는 아래 그림과 같이 움직일 수 있고,

색칠된 구역은 이동시 꼭 빈 칸(0)이어야 하는 곳이다.

파이프를 옮길 수 있는 방법의 수를 구하자.

🧾 입력 예시

6
0 0 0 0 0 0
0 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

첫번째 줄에는 격자판의 크기, 두번째 줄부터 격자판이 주어진다.

1은 장애물이 있는 곳으로, 파이프 이동에 방해를 준다.

🔎 출력 예시

13

🔑 문제 풀이

🔧 처음 시도한 풀이

class Pipe{
	int[] head;
	int[] tail;
	int curDir;
	public Pipe() {
		head = new int[2];
		tail = new int[2];
		head[0] = 1;
		head[1] = 2;
		tail[0] = 1;
		tail[1] = 1;
		int curDir = 0;
	}
	public Pipe(int[] head, int[] tail, int dir) {
		this.head = head;
		this.tail = tail;
		this.curDir = dir;
	}
}

Pipe클래스를 만들어 pipe의 위치와 방향을 알 수 있도록 하였고, 현재 위치에서 3가지 방향으로 가는 DFS방법을 사용하였다.

하지만 파이프의 방향에 따라 갈 수 있는 방향이 달라졌고, 해당 방향에 따라 가짓수가 많이 나와 시간초과가 발생하였다.

🔑 풀이

1. 격자판 map과 DP의 과정을 담을 3차원 배열 ret을 생성하였다.
   ret의 경우 파이프가 이동할 수 있는 방향을 담아야 하기에 3차원으로 지정하였다.
   ret[행위치][열위치][방향], 방향은 →[0], ↓[1], ↘[2]로 설정하였다.
   ( ex. ret[i][j][0] : head가(i,j) 위치에서 가로(0)로 놓인 상태를 의미한다. )
   
   

2. 시작점 ret[1][2]는 가로로 놓여있으므로 ret[1][2][0]만 1로 초기화 하였다.
   
   

3. 현재상태 ret[i][j]는 이전상태들의 합으로 이루어진다.

   • ret[i][j][0] = ret[i][j-1][0] + ret[i-1][j-1][2]이 성립한다.
     (i, j)가로상태는 (i, j-1)위치의 가로상태에서의 이동, (i-1, j-1)위치의 대각상태에서의 이동의 합이다.

   • ret[i][j][1] = ret[i-1][j][1] + ret[i-1][j-1][2]이 성립한다.
     (i, j)세로상태는 (i-1, j)위치의 세로상태에서의 이동, (i-1, j-1)위치의 대각상태에서의 이동의 합이다.

   • ret[i][j][2] = ret[i-1][j-1][0] + ret[i-1][j-1][1] + ret[i-1][j-1][2]가 만족한다.
     (i, j) 대각상태는 (i-1, j-1)위치의 가로상태에서의 이동, (i-1, j-1)위치의 세로상태에서의 이동, (i-1, j-1)위치의 대각상태에서의 이동의 합이다.

4. 위 식을 기반으로 ret계산 과정에서 장애물(1)이 있으면 지나가지 못하도록 canMove() 메소드 이용

private boolean canMove(int[][]map, int row, int col) {
	for(int i=row-1 ; i<=row ; i++) {
		for(int j=col-1 ; j<=col ; j++) {
			if(map[i][j]==1)
				return false;
		}
	}
	return true;
}

💻 전체 코드

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		Main z= new Main();
		z.solution();
	}
	int N = 0;
	private void solution() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		int[][] map = new int[N+1][N+1];
		int[][][] ret = new int[N+1][N+1][3]; 
		for(int i=1 ; i<N+1 ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=1 ; j<N+1 ; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j]==1) {
				}
			}
		}
		ret[1][2][0] = 1;
		// ret[i][j][0,1,2] : 0:가로, 1:세로, 2:대각
		for(int i=1 ; i<=N ; i++) {
			for(int j=1 ; j<=N ; j++) {
				if((i==1 && j==1) || (i==1&&j==2))
					continue;
				if(map[i][j]==1)
					continue;
				ret[i][j][0] += ret[i][j-1][0];
				ret[i][j][0] += ret[i][j-1][2];
				
				ret[i][j][1] += ret[i-1][j][1];
				ret[i][j][1] += ret[i-1][j][2];
				if(canMove(map,i,j)) {
					ret[i][j][2] += ret[i-1][j-1][2];
					ret[i][j][2] += ret[i-1][j-1][1];
					ret[i][j][2] += ret[i-1][j-1][0];
				}
			}
		}
		System.out.println(ret[N][N][0]+ret[N][N][1]+ret[N][N][2]);
	}
	private boolean canMove(int[][]map, int row, int col) {
		for(int i=row-1 ; i<=row ; i++) {
			for(int j=col-1 ; j<=col ; j++) {
				if(map[i][j]==1)
					return false;
			}
		}
		return true;
	}
}

📇 결과