[Java] 백준 BOJ / 17070번: 파이프 옮기기 1

파이프 옮기기 1

문제

---

문제 설명

두칸을 차지하는 파이프가 있다.

N x N 크기의 격자에 벽과 빈 공간의 위치가 주어진다. 파이프는 가로 방향, 세로방향, 대각선 방향이 가능하다.

초기의 파이프가 (1, 1) (1, 2) 를 차지하고 있을 때, 파이프의 한쪽 끝이 (N, N) 까지 이동시키는 방법의 수를 출력하는 문제이다.

유의해야 할 점은 파이프가 이동할 때, 파이프가 벽을 긁으면 안된다.

그림에서 보이는 것 처럼 가로와 세로는 내가 갈 방향 하나만 비어있으면 되지만, 대각선의 경우 내가 갈 방향의 왼쪽과 위쪽이 모두 비어있어야 한다.

---

구현

경로의 수를 구해야 하고, 경로마다 상태가 다르기 때문에 DP로 풀어야겠다는 생각을 했다.

일반적인 2차원 DP 배열로 풀 수는 없고 3차원으로 확장시켜서 파이프의 방향을 확인해주어야 한다.

일단 파이프의 초기 끝값 위치인 (1,2) 에 가로방향이라는 뜻으로 DP의 초기값을 지정해준다.

//초기 파이프의 위치 (1, 2) 에 가로 방향 0
dp[1][2][0] = 1;

그리고 이제 입력으로 받은 arr 배열을 확인하면서 DP 배열을 채워주면 된다.

만약에 벽이라면 그냥 넘기고 조건을 확인해야한다.

가로방향인 dp[i][j][0] 은 이전 상태가 가로인 경우와 이전 상태가 대각선인 경우에서 오는 2가지 경우가 있다.

dp[i][j][0] += dp[i][j - 1][0] + dp[i][j - 1][2];

세로방향도 마찬가지로 생각해보면 이전 상태가 세로인 경우, 이전 상태가 대각선인 경우에서 오는 2가지 경우가 있다.

dp[i][j][1] += dp[i - 1][j][1] + dp[i - 1][j][2];

대각선 방향은 조건이 좀 까다롭다. 일단 대각선 위치라는 것은 이전의 위치인 (i - 1, j - 1) 이 존재해야한다는 건데 그렇게 되려면 i와 j는 2 이상이 되어야 한다.

또한 벽이 걸리면 안되기 때문에 내가 갈 좌표의 왼쪽과 위쪽을 확인해서 0일 경우만 진행한다.

대각선인 경우는 세가지 경우 모두 가능하다. 전 방향이 가로일때, 세로일때, 대각선일 때 모두 가능하다.

//대각선
if (i >= 2 && j >= 2 && arr[i - 1][j] == 0 && arr[i][j - 1] == 0) {
	dp[i][j][2] += (dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2]);
}

그리고 나서는 이제 (N, N) 의 가로방향, 세로방향, 대각선 방향을 모두 더해주면 된다.

---

코드

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

public class Main_17070 {
  static int[][] arr;
  static int[][][] dp;
  static int n;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());

    arr = new int[n + 1][n + 1];
    //0: 가로, 1: 세로, 2: 대각선
    dp = new int[n + 1][n + 1][3];

    for (int i = 1; i <= n; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int j = 1; j <= n; j++) {
        arr[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    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;
        }

        //가로방향 = 가로방향 y - 1 값 + 대각선에서 온 값
        dp[i][j][0] += (dp[i][j - 1][0] + dp[i][j - 1][2]);

        //세로방향
        dp[i][j][1] += dp[i - 1][j][1] + dp[i - 1][j][2];

        //대각선
        if (i >= 2 && j >= 2 && arr[i - 1][j] == 0 && arr[i][j - 1] == 0) {
          dp[i][j][2] += (dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2]);
        }
      }
    }

    int result = dp[n][n][0] + dp[n][n][1] + dp[n][n][2];

    System.out.println(result);
  }
}