[JAVA] 17069번: 파이프 옮기기 2

🔗 문제

17069번: 파이프 옮기기 2

17069번: 파이프 옮기기 2

✏️ 풀이

 

맨 처음 맵에 파이프가 가로로 있다. 끝점이 (0, 1)

파이프가 있을 수 있는 상태 : type {가로, 세로, 대각선} 각 타입에 따라 옮길 수 있는 조건이 있다.

문제를 잘 읽고 예제도 잘 보자. 문제를 잘 안 읽으면 예제 5번이 이해가 안 갈 수 있다.

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.

 

이 문제는 파이프 옮기기 1 이라는 문제 이후에 풀길 권장한다.

문제 1과 현재 문제 2의 차이는 (1) N의 범위 (2) 시간의 차이다.

최적화 라기 보다는 1에서는 어떻게 됐던 논리가 문제 2에서는 통하지 않는다는 거다.

즉, 접근법에 따라 효율이 크게 달라지는 문제로 이런 문제를 봤을 때 어떤 알고리즘이 필요한지 생각해내는게 Key 포인트라고 생각한다.

 

시간 초과 나는 접근법

• 타입에 따라서 진행할 수 있는 방향으로 dfs 해주기
• 문제 1에서도 문제 없고, 답은 나오지만 문제 2의 마지막 예제에서 답이 나오는데 한참이 걸렸다.

 

정답 접근법

문제를 다시 보자.

 

파이프의 시작점은 (0, 1) 그리고 세로 상태인 한 가지의 경우의 수를 갖고 시작한다.

시작점과 상태에 따라서 다음으로 진행할 수 있는 방법이 다르다.

즉, 내가 앞에 어떤 선택을 했는지에 따라 다음 값이 달라진다.

 

이렇게 문장으로 생각을 정리하니까 바로 아 .. 이거 DP구나 라는 생각이 왔다.

필요한 요소는 x, y, type 이므로 dp[x][y][type]에 나의 선택을 담으면 되겠다는 생각이 들었다.

• type
  • 0 : 가로
  • 1 : 세로
  • 2 : 대각선

dp[x][y][가로] 이 될 수 있는 경우는 무엇이 있을까?

바로 이전에 dp[x][y-1][가로]였거나 dp[x][y-1][대각선]이었기 때문이다.

 

문제에서 주어진 대로 보면 ? 아래처럼 정리할 수 있다!

dp[x][y][가로] = dp[x][y-1][가로] + dp[x][y-1][대각선]

dp[x][y][세로] = dp[x-1][y][세로] + dp[x-1][y][대각선]

dp[x][y][대각선] = dp[x-1][y-1][가로]+ dp[x-1][y-1][세로] + dp[x-1][y-1][대각선]

 

 

여기서 주의할 점은 대각선은 봐야할 부분이 3부분이라는 거다.

가로, 세로는 자기가 나아갈 부분만 체크하면 되는데 대각선은 벽이 있는지 체크해야할 부분이 3개라 조건이 하나 더 붙는다. (코드 참고)

 

 

🧠  신경 쓴 부분

x, y 위치가 어떻게 만들어졌냐를 따지다보니 x-1, y-1에 접근하게 되는데

이때 마다 배열의 인덱스 범위를 신경쓰는게 머리가 아파서 맵의 크기를 1씩 늘려주었다.

시작 인덱스가 (0, 0)이 아니라 (1, 1)이다.

 

 

💾  소스

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

public class Main {

	static int field[][], N;

	static long getAnswer() {
		
		long answer = 0;
		long dp[][][] = new long[N+2][N+2][3];

		dp[1][2][0] = 1;

		for (int i = 1; i <=N; i++) {
			for (int j = 1; j <=N; j++) {

				if (field[i][j] == 1)
					continue;

				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 (field[i - 1][j] == 1 || field[i][j - 1] == 1)
					continue;

				dp[i][j][2] += dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];
			}
		}
		
		for(int i=0; i<3; ++i)
			answer += dp[N][N][i];
		
		return answer;
	}

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

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

		System.out.print(getAnswer());
	}

}