[Java Algorithm] 파이프 옮기기 2 BOJ #17069

문제

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

17069번: 파이프 옮기기 2

 

내 문제 풀이

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

public class Main {

	static int n;
	static int[][] map;
	static long[][][] memo; // 가장 하위 인덱스 0, 1, 2 == 가로, 세로, 대각선
	
	public static long dp() {
		for(int i = 1; i < n+1; i++) {
			for(int j = 3; j < n+1; j++) {
				if(map[i][j] == 1) continue; // 벽이면 어떤 파이프도 불가하므로 continue
				memo[i][j][0] = memo[i][j-1][0] + memo[i][j-1][2]; // 가로
				if(i == 1) continue; // 첫 번째 줄일 경우, 세로가 절대 불가능하기 때문에 continue
				memo[i][j][1] = memo[i-1][j][1] + memo[i-1][j][2]; // 세로
				if(map[i-1][j] == 1 || map[i][j-1] == 1) continue; // 대각선으로 오려면 위, 아래도 모두 빈 칸이어야 하므로 continue
				memo[i][j][2] = memo[i-1][j-1][0] + memo[i-1][j-1][1] + memo[i-1][j-1][2]; // 대각선
			}
		}
		
		return memo[n][n][0] + memo[n][n][1] + memo[n][n][2];
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(in.readLine());
		map = new int[n+1][n+1];
		for(int i = 1; i < n+1; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j = 1; j < n+1; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		memo = new long[n+1][n+1][3];
		memo[1][2][0] = 1;
		if(map[n][n] == 1) {
			System.out.println(0);
		} else {
			System.out.println(dp());
		}
	}
}

👉 DP 문제

현재 파이프에서 다음 파이프로 갈 때 어떻게 갈지를 생각하기보다,

현재 자리에 (가로 or 세로 or 대각선)의 방향으로 오는데에는 몇 개의 경우가 있을지를 생각해 주는게 포인트 ✨

• map과 같은 크기의 3차원 배열 memo를 만들고, memo의 가장 하위는 3의 크기로 만들어서
  인덱스 0, 1, 2 순서대로 가로, 세로, 대각선으로 올 수 있는 경우의 수를 저장하도록 했다.
• memo에 처음 시작하는 파이프의 정보를 담아 초기화해주고, dp 메소드에서 경우의 수를 누적했다.
• dp에서는 첫 번째 줄의 세 번째 자리(첫 파이프의 다음 자리)부터 탐색을 시작해주었는데
  문제에서 주어진 조건에 맞춰 각각 세로, 가로, 대각선으로 해당 자리에 갈 수 있는 경우의 수를 누적했다.

 

💡 피드백

• 처음엔 이 문제를 재귀로 풀었는데(파이프 옮기기 1 문제), 3차원 배열을 만들어서 각 자리마다
  가능한 경우의 수를 구해주면 훨씬 효율적으로 풀이할 수 있었다.
  👉 이 문제가 어려우신 분들은 RGB 거리 문제를 먼저 풀고 오시면 쉽게 이해 가능하실 듯 합니당!