[BOJ] 백준 17069번 파이프 옮기기 2 (Java)

 

#17069 파이프 옮기기 2

난이도 : 골드 5

유형 : DP

17069번: 파이프 옮기기 2

▸ 문제

유현이가 새 집으로 이사했다. 새 집의 크기는 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 ≤ 32)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.

▸ 출력

첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다.

 

 

 

문제 풀이

시작점 (1,1)에서 세가지 방향으로 파이프를 움직이면서 도착점(N,N)까지 도착하는 경우의 수를 구하면 된다.

 

📚 조건

• 맵 크기 N x N (3<= N <= 32)
• 파이프 시작 위치 (1,1), 도착 위치 (N,N)  → 갈 수 없을 경우 0
• 빈칸 0, 벽 1
• 방향 → ↘︎ ↓ 

 

현재 위치를 (x,y)라 할 때 다음 3가지 방향으로 움직이는 경우의 수를 고려해보자. (파이프의 현재 위치는 앞 부분을 가르킨다.)

 

1) 파이프가 현재 가로(flow = 1)일 때 다음 이동으로 갈 수 있는 방향은 가로와 대각선이다.

dp[y][x][flow] +=dfs(x+1,y,1) + dfs(x+1,y+1,3);

 

2) 파이프가 현재 세로(flow =2)일 때 다음 이동으로 갈 수 있는 방향은 세로, 대각선이다.

dp[y][x][flow] += dfs(x,y+1,2)+ dfs(x+1,y+1,3);

 

3) 파이프가 현재 대각선일 때 다음 이동으로 갈 수 있는 방향은 가로,세로, 대각선 모두 가능하다.

dp[y][x][flow] += dfs(x+1,y,1) + dfs(x,y+1,2) + dfs(x+1,y+1,3);

 

처음에는 Top-down 재귀탐색을 하는데 메모이제이션을 하면 답이 나오는데 시간초과가 떴다. 그래서 메모이제이션을 하니? 값이 이상하게 나오는 것을 확인할 수 있었다. 메모이제이션은 이미 저장되어 있는 값은 그냥 불러와서 연산을 줄여주는 용도로 사용한다. 그러니 저장된 값에 문제가 있는 것일텐데... 흠 뭘까 하다가 방향은 가로,세로,대각선 세 개인데 저장되는 공간은 하나에 몰아서 저장해주고 있었다. 그래서 2차원 배열을 3차원 배열로 바꿔줬다.

→ 같은 공간이더라도 각 방향에 따라 값이 다를테니 이미 방문을 했더라도 다른 방향으로 또 방문을 할 수도 있기 때문이다.

 

❍ Top-down 풀이

(1,1)부터 시작하여 탐색을 시직하면 된다.그리고 dp를 사용하여 해당 정점에 몇 가지 경우의 수의 파이프가 도착하는지 저장해주면 된다.

코드를 보면 쉽게 이해할 수 있을 것이다.

* (1,1)은 가로방향으로 밖에 이동이 안된다. 

static long dfs(int x, int y, int flow) {
		
		if(x<1 || y<1 || x>n || y>n || map[y][x] ==1) return 0;
		if(flow == 3 && (map[y-1][x] ==1 || map[y][x-1] ==1)) return 0;
		
		if(checked[y][x][flow]) return dp[y][x][flow];
		
		if(x==n && y== n) {
			return 1;
		}
		
		dp[y][x][flow] =0;
		checked[y][x][flow] = true;
		
		if(x==1&& y==1) {
			return dp[y][x][flow] += dfs(x+1,y,1);
		}
		
	
		// 가로 
		if(flow==1) {
			dp[y][x][flow] +=dfs(x+1,y,1) +
						dfs(x+1,y+1,3);
		}
		// 세로 
		else if(flow==2) {
			dp[y][x][flow] += dfs(x,y+1,2)+
						dfs(x+1,y+1,3);
		}
		// 대각선 
		else if(flow==3) {
			dp[y][x][flow] += dfs(x+1,y,1) +
						dfs(x,y+1,2) +
						dfs(x+1,y+1,3);
		}
		
		return dp[y][x][flow];
			
		
	}

 

 

 

풀이 코드  

값의 범위가 40억이 넘는 수가 있어 long으로 바꿔줬다.

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

public class Main {
	
	static int n;
	static int[][] map;
	static long[][][] dp;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		map = new int[n+1][n+1];
		dp = new long[n+1][n+1][4];
		
		StringTokenizer st =null;
		for(int i=1; i<n+1; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<n+1; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		
		dp[1][2][1] =1;  //초기 파이프 가로방향 위치
		for(int i=1;i<n+1;i++) {
			for(int j=3;j<n+1;j++) {
				if(map[i][j] ==1) continue;
				
				//가로
				dp[i][j][1] = dp[i][j-1][1]+dp[i][j-1][2]; 
				//세로
				dp[i][j][3] = dp[i-1][j][2] + dp[i-1][j][3]; 
				//대각선
				if(map[i][j-1] ==0 && map[i-1][j] ==0)  {
					dp[i][j][2] = dp[i-1][j-1][1] + dp[i-1][j-1][2] + dp[i-1][j-1][3];
				}
				
					
			}
		}
		System.out.println(dp[n][n][1]+dp[n][n][2]+dp[n][n][3]);
	}
}

 

 

+

❍ Bottom-up 풀이

Bottom up으로 풀이하면 다음과 같다.

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

public class Main {
	
	static int n;
	static int[][] map;
	static long[][][] dp;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		map = new int[n+1][n+1];
		dp = new long[n+1][n+1][4];
		
		StringTokenizer st;
		for(int i=1; i<n+1; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<n+1; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dp[1][2][1] =1;  //초기 파이프 가로방향 위치
		for(int i=1;i<n+1;i++) {
			for(int j=3;j<n+1;j++) {
				if(map[i][j] ==1) continue;
				
				//가로
				dp[i][j][1] = dp[i][j-1][1]+dp[i][j-1][2]; 
				//세로
				dp[i][j][3] = dp[i-1][j][2] + dp[i-1][j][3]; 
				//대각선
				if(map[i][j-1] ==0 && map[i-1][j] ==0)  {
					dp[i][j][2] = dp[i-1][j-1][1] + dp[i-1][j-1][2] + dp[i-1][j-1][3];
				}
			}
		}
		System.out.println(dp[n][n][1]+dp[n][n][2]+dp[n][n][3]);
	}
}