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

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

17070번: 파이프 옮기기 1

[풀이]

​

<잘못된 방법>

​

기본적인 BFS 문제라고 생각하고 접근했다.

단순히 아래, 대각선 아래, 오른쪽 방향으로만 이동하기 때문에 visit 체크를 따로 해줄 필요도 없었고,

(N,N) 까지 갈 수 있는 모든 경로를 구하기만 하면 되서 BFS를 돌며 파이프 앞부분이 (N,N)에 도달할 때 마다 count를 ++해주었다.

결과는 잘 나왔지만, 시간초과가 났다.

​

​

< 동적 프로그래밍 방법 >

​

이동 가능 경로의 합 문제는 DFS, BFS로 풀 수도 있지만 대개 DP로도 풀 수 있다.

​

이 문제에서, 파이프는 →, ↘, ↓ 세 방향으로 이동 가능하다.

​

파이프는 두 칸을 차지하기 때문에 이해를 쉽게 하기 위해서 앞 부분을 머리, 뒷 부분을 꼬리라고 가정한다.

​

여기서 파이프는 두 칸을 차지하지만, 두 칸 모두 신경 쓸 필요 없이 목표지점을 향해 가는 머리 부분만 신경쓰면 된다.

​

파이프가 다른 칸으로 이동하게 되면 꼬리 부분은 이전 머리 부분의 자리로 오기 때문에 머리 부분만 제대로 된 지점으로 가면 된다.

​

결론적으로 이 문제에서 신경쓸 부분은 대각선 방향으로 이동하는 경우이다.

​

예를 들어, (x,y) 에서 (x+1,y+1) 지점으로 이동할 때 (x+1,y) 와 (x, y+1) 부분에 벽이 세워져 있으면 안 된다.

​

대각선 방향으로 가는 경우를 제외한 모든 경우는 따로 조건을 설정해줄 필요가 없다.

​

DP를 이용하는 방법은 어느 한 지점까지 도달할 수 있는 경우의 수를 이전 지점들의 값을 통해서 더하는 것이다.

​

(1,1)	(1,2)	(1,3)
(2,1)	(2,2)	(2,3)
(3,1)	(3,2)	(3,3)

노란색 칸의 (2,2) 지점까지 도달할 수 있는 경우의 수를 알기 위해서는 주황색 부분으로 칠해진 이전 지점들을 사용해야 한다.

​

그런데 여기서 가장 중요한 것은 이동방향에 따라 그 다음 이동방향을 바꿀 수 있는 방법이 제한적이기 때문에 DP배열에 방향에 대한 정보를 포함시켜야 한다.

​

(2,2) 지점까지 갈 수 있는 경우의 수는 3가지로 나타낼 수 있다.

1. (2,2) 지점까지 도달했을 때 방향이 오른쪽 → 방향인 경우

2. (2,2) 지점까지 도달했을 때 방향이 대각선 아래 ↘ 방향인 경우

3. (2,2) 지점까지 도달했을 때 방향이 아래 ↓ 방향인 경우

​

그래서 이 세가지 경우를 모두 더한 값이 총 (2,2) 지점까지 갈 수 있는 경우의 수 이다.

​

이제 3가지 경우에 대해 이전 지점을 사용해서 합으로 나타내는 방법만 남았다.

​

1. (2,2) 지점까지 도달했을 때 방향이 오른쪽인 경우

- (2,1) 지점까지 도달했을 때 방향이 오른쪽인 경우 + (2,1) 지점까지 도달했을 때 방향이 대각선 아래인 경우

​

2. (2,2) 지점까지 도달했을 때 방향이 대각선 아래인 경우*

- (1,1) 지점까지 도달했을 때 모든 경우 (방향 오른쪽,대각선아래,왼쪽)

- 여기서 중요한 점이 (2,1)과 (1,2)에 벽이 세워져있는지 여부를 체크하는 것이다. 벽이 세워져 있다면 이 부분의 값은 0이다.

​

3. (2,2) 지점까지 도달했을 때 방향이 아래인 경우

- (1,2) 지점까지 도달했을 때 방향이 대각선 아래인 경우 + (1,2) 지점까지 도달했을 때 방향이 아래인 경우

​

이 세가지를 모두 더하면 총 (2,2) 지점까지 도달할 수 있는 경우의 수가 나온다.

​

이런 식으로 이차원 배열을 쭉 탐색하면 (N,N) 지점까지 도달할 수 있는 경우의 수를 구할 수 있다.

​

​

[소스코드]

import java.util.Scanner;

public class Main {	//bj17070 파이프 옮기기 1
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[][] arr=new int[n+1][n+1];
		int[][][] dp=new int[n+1][n+1][3];
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				arr[i][j]=sc.nextInt();
			}
		}
		dp[1][2][0]=1;
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				if(arr[i][j]==1) continue;
				dp[i][j][0]+=dp[i][j-1][0]+dp[i][j-1][1];
				if(arr[i][j-1]!=1&&arr[i-1][j]!=1) {
					dp[i][j][1]+=dp[i-1][j-1][0]+dp[i-1][j-1][1]+dp[i-1][j-1][2];
				}
				dp[i][j][2]+=dp[i-1][j][1]+dp[i-1][j][2];
			}
		}
		System.out.println(dp[n][n][0]+dp[n][n][1]+dp[n][n][2]);
	}
}