[백준 17070] - 파이프 옮기기1(JAVA)[골드5]

문제

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

17070번: 파이프 옮기기 1

 

문제 풀이

나는 문제를 읽고 DP로 접근을 했는데, 다른 풀이를 보니 DFS로 푼 사람들이 꽤 많았다.

개인적으로 DFS보단 BFS를 선호하고, DFS로 풀 생각을 하지 못했어서 DP로 풀었고, 그에 따른 방법을 설명하겠다.

 

우선 DP로 선택한 이유는 파이프를 놓는 위치가 이전의 선택들에게 영향을 받는다는 점이었다.

즉 (i, j)로 파이프를 놓을 때,

방향에 따라 이전 위치의 경우의 수에 영향을 받는다는 것이다.

예를 들어 좌표를 (i, j)로 고정시켜서 설명하겠습니다.

• 가로로 놓을 경우
  • 가로로 파이프를 연결할 수 있는 경우는 이전 위치에서 가로, 대각선으로 연결된 경우이다.
    • 여기서 이전 위치는 왼쪽에 있는 (i, j-1)
  •  따라서 (i, j)에 가로로 놓을 수 있는 경우의 수는 (i, j-1) 위치에서 가로로 연결된 경우의 수와 대각선으로 연결된 경우의 수를 더해주면 된다.
• 세로로 놓을 경우 
  • 세로로 파이프를 연결할 수 있는 경우는 이전 위치에서 세로, 대각선으로 연결된 경우이다.
    • 여기서 이전 위치는 위에 있는 (i-1, j)
  • 따라서 (i, j)에 세로로 놓을 수 있는 경우 의 수는 (i-1, j)에서 세로와 대각선으로 연결된 경우의 수를 더해주면 된다.
• 대각선으로 놓을 경우
  • 대각선으로 파이프를 연결할 수 있는 경우는 이전 위치에서 가로, 세로, 대각선으로 연결된 경우이다.
    • 여기서 이전 위치는 (i-1, j-1)이다.
    • 여기서 하나 더 생각해줘야 할 점은 대각선으로 놓을 경우 주변에 벽이 있으면 안 된다.
      • 주변은 (i-1, j) , (i, j-1)
  • 따라서 (i, j)에 대각선으로 놓을 수 있는 경우의 수는 (i-1, j-1)에서 가로, 세로, 대각선으로 연결된 경우의 수를 더해주면 된다.

이렇게 각 좌표마다 3가지의 파이프 경우의 수를 저장해야 했기에, dp배열을 3차원으로 선언했다.

dp [i][j][0] : (i, j)에 가로로 파이프를 연결할 수 있는 경우의 수
dp [i][j][1] : (i, j)에 세로로 파이프를 연결할 수 있는 경우의 수
dp [i][j][2] : (i, j)에 대각선으로 파이프를 연결할 수 있는 경우의 수

 

그리고 나는 for문을 탐색할 때 열을 2번부터 검사했다.

왜냐하면 1번 열은 절대로 갈 수 없기 때문이다!(그렇게 크게 중요하진 않지만,,)

 

전체 코드

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

public class Main {

	static int n;
	static BufferedReader br;
	static StringTokenizer st;
	static int[][] graph;
	static int[][][] dp;
	static int answer = 0;

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		input();
		search();
		System.out.print(answer);
	}

	public static void input() throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		graph = new int[n+1][n+1];
		dp = new int[n+1][n+1][3];
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= n; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}
	}

	public static void search() { // n * n으로 탐색
		//파이프가 가로로 놓아진 경우 이동방법은 2개. 가로 or 아래 대각선
		//세로로 놓아진 경우 이동방법은 2개. 세로 or 아래 대각선
		//대각선으로 놓아진 경우 이동방법은 3개. 가로 , 세로 , 대각선
		//대각선인 경우 도착지점에서 3개 블록을 사용하지 못함.
		//(n,n) -> (n,n-1), (n+1,n+1), (n-1,n+1)
		dp[1][2][0]=1; //(1,2)에 파이프가 있다.
		for(int i=1; i<=n; i++) {
			for(int j=2; j<=n; j++) { //3가지 방향에서 올 수 있다. 가로 , 세로 , 대각선
				if(graph[i][j]==1) //벽에는 놓을 수가 없음.
					continue;				//
				dp[i][j][0] = Math.max(dp[i][j][0],dp[i][j-1][0] + dp[i][j-1][2]);// 들어오는 좌표는 (i,j-1)이고 유효한 파이프는 가로와 대각선
				dp[i][j][1] = Math.max(dp[i][j][1], dp[i-1][j][1] + dp[i-1][j][2]);//들어오는 좌표는 (i-1,j)이고 유효한 파이프는 세로와 대각선
				if(graph[i-1][j]==1 || graph[i][j-1]==1) //도착하는 지점에서 왼쪽칸과 위칸이 비어야 함.
					continue;
				dp[i][j][2] = Math.max(dp[i][j][2], dp[i-1][j-1][0] + dp[i-1][j-1][1]+ dp[i-1][j-1][2]); //들어오는 좌표는 (i-1,j-1)이고, 유효한 파이프는 가로,세로,대각선
			}
		}
		answer=dp[n][n][0] + dp[n][n][1] + dp[n][n][2];
	}	
}