[백준 / Java] 17070번: 파이프 옮기기 1 (골드5)

문제 풀이 날짜: 2023.08.30
포스트 작성일: 2023.08.30

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 17070번: 파이프 옮기기 1 (골드5)

 

키워드

동적 계획법

 

풀이 접근법

• 좌표에 따라 값을 채워 넣는 2차원 DP문제
• 파이프의 모양이 계속 변하므로 매 칸마다 파이프의 상황을 고려해서 각기 다르게 DP를 채워넣어야 한다.
• 즉, (현재 지점까지 올 수 있는 경우의 수 + 현재의 파이프의 방향) 두 가지 정보를 고려해야 한다.
• 그런데 파이프의 모양에 따라 이전 값을 끌어다 쓸 수 있는 경우는 한정적이다.
  • 현재 모양이 - 라면 왼쪽, 대각선 위의 DP만 가져올 수 있다.
  • 현재 모양이 | 라면 윗쪽, 대각선 위의 DP만 가져올 수 있다.
  • 현재 모양이 / 라면 왼쪽, 대각선 위, 윗쪽의 DP를 가져올 수 있다.
• 이 규칙에 맞추어 Bottom-Up으로 DP값을 구해준다.
• 벽이 세워진 곳을 DP 계산에 포함시키지 않도록 주의한다.

 

코드

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

public class Main {

	private static final int HOR = 0;
	private static final int DIAG = 1;
	private static final int VERT = 2;

	private static int N;

	private static int[][] matrix;
	private static int[][][] DP;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		matrix = new int[N][N];
		DP = new int[3][N][N]; // 파이프의 방향: 0, 1, 2

		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		DP[HOR][0][0] = 1;
		DP[HOR][0][1] = 1;

		for (int i = 0; i < N; i++) {
			for (int j = 2; j < N; j++) {
				if(matrix[i][j] == 1) {
					continue;
				}
				
				if (i - 1 >= 0 && matrix[i - 1][j] != 1) { // 윗쪽에서 밀 수 있다면
					DP[VERT][i][j] += (DP[VERT][i - 1][j] + DP[DIAG][i - 1][j]);
				}

				if (j - 1 >= 0 && matrix[i][j - 1] != 1) { // 왼쪽에서 밀 수 있다면
					DP[HOR][i][j] += (DP[HOR][i][j - 1] + DP[DIAG][i][j - 1]);
				}

				if (i - 1 >= 0 && j - 1 >= 0 && matrix[i - 1][j] != 1 && matrix[i][j - 1] != 1 && matrix[i - 1][j - 1] != 1) { // 대각선에서 밀 수 있다면
					DP[DIAG][i][j] += (DP[HOR][i - 1][j - 1] + DP[VERT][i - 1][j - 1] + DP[DIAG][i - 1][j - 1]);
				}
			}

		}

		int result = 0;
		for (int k = 0; k < 3; k++) {
			result += DP[k][N - 1][N - 1];
		}

		System.out.println(result);
	}
}

---

 

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/0a9ccbe8b196e2a4be747761ba50ef01f903a74d/%EB%B0%B1%EC%A4%80/Gold/17070.%E2%80%85%ED%8C%8C%EC%9D%B4%ED%94%84%E2%80%85%EC%98%AE%EA%B8%B0%EA%B8%B0%E2%80%851/%ED%8C%8C%EC%9D%B4%ED%94%84%E2%80%85%EC%98%AE%EA%B8%B0%EA%B8%B0%E2%80%851.java