(Java/자바) - 백준(BOJ) 17070번 : 파이프 옮기기 1

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

---

• 문제 : 

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

 

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

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

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

 

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

.

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

 

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

가로

 

세로

 

대각선

 

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

 

 

 

---

• 풀이 :

DP 문제였습니다.

 

풀이입니다.

 

위 문제에서 임의의 좌표 (X,Y) (X >= 1, Y >= 1)까지 오는 방법의 수가 만들어지기 위해 3가지 경우를 더해주어야 합니다..

 

1.  위쪽까지 오는 경우의 수

 

2. 왼쪽 위 (대각선)까지 오는 경우의 수 

 

3. 왼쪽까지 오는 경우의 수

 

각 경우마다 고려해야 할 제약조건들이 존재합니다.

 

1번의 경우 위쪽까지 오는 경우의 수들 중 가로 모양으로 해당 좌표(X-1, Y)에 도달하는 경우는 더해주면 안됩니다. 가로 모양의 파이프는 어떠한 방법으로도 한칸 아래인 현재좌표로 옮길 수 없기 때문입니다.

 

3번의 경우 1번과 비슷하게 세로 모양으로 해당 좌표(X, Y-1)에 도달하는 경우는 더해주면 안됩니다. 세로 모양의 파이프는 어떠한 방법으로도 한칸 오른쪽인 현재좌표로 옮길 수 없기 때문입니다.

 

2번의 경우가 조금 특이합니다.

 

예를 들어 

 

4    2
3    1  

 

에서 현재 1이라 값이 있는 위치를 탐색중이라면  현재 좌표 포함 2번, 3번 좌표에 벽이 있어서는 안됩니다.

 

따라서, 위, 왼쪽에 벽이 없는 경우에 왼쪽 대각선위의 좌표로 도달할 수 있는 모든 경로를 더해주면 됩니다..

 

이 때, 가로로 해당 좌표에 도달하는 경우, 세로로 해당 좌표에 도달하는 경우, 대각선으로 해당 좌표에 도달하는 경우를 나누어주기 위해 3차원 배열을 사용하였습니다. 

 

 

---

• 소스코드 : 

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

public class Main{
	static int N, answer;
	static int[][][] dp;
	static String[][] board;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		board = new String[N][N];
		dp = new int[N][N][3];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				board[i][j] = st.nextToken();
			}
		}
		for (int i = 1; i < N; i++) {
			if (board[0][i].equals("1")) break;
			dp[0][i][0] = 1;
		}
		for (int i = 1; i < N; i++) {
			for (int j = 1; j < N; j++) {
				if(board[i][j].equals("1"))continue; // 현재 좌표가 벽인 경우
                
                // 현재 좌표가 대각선으로 올 수 없는 경우
				if(board[i][j-1].equals("0") && (board[i-1][j].equals("0")) && (board[i-1][j-1].equals("0"))) dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2];
				
                // 나머지 경우
                dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2];
				dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2];
			}
		}
		
		for (int i = 0; i < 3; i++) {
			answer += dp[N-1][N-1][i];
		}
		System.out.println(answer);
	}
}