[백준/JAVA] 17070_파이프 옮기기 1

백준🔗

17070번: 파이프 옮기기 1

 

문제

 

 

 

간단 풀이

사실 오늘 DP 연습하려고 DP 분류에서 문제를 선택해서 풀기 시작했다.

그런데 문제를 읽으면서 아무리 생각해봐도 DFS밖에 떠오르지 않아서 일단 DFS로 구현해서 통과했다.

 

DFS 구현 자체는 문제에서 주어진 상황을 그대로 따라서 구현하면 되기 때문에 어려울 것은 없는 것 같다.

현재 파이프의 방향에 따라 분류를 나누고,

이동하고자 하는 방향으로 이동 가능한지 여부를 따져서 이동한다. (배열이 벗어나지 않아야 하고, 비어있어야 하는 칸은 0이어야 한다.)

끝 점에 도달했을 경우의 수를 카운트해서 출력해준다.

 

이 문제가 왜 DP였을까 고민을 하며 다른 분들의 코드를 참고했더니

dp[i][j][k] : (i,j)칸에 k 방향(가로, 세로, 대각선)으로 올 수 있는 경우의 수

이런 식으로 dp 배열을 정의해서 3차원 배열로 사용한 듯했다.

따라서 마지막 칸에 도달할 수 있는 경우의 수는 dp[i][j][가로] + dp[i][j][세로] + dp[i][j][대각선] 으로 구할 수 있게 되는 것이다.

위치(행, 열)와 방향의 정보가 필요하니 미지수가 3개여서 3차원 배열로 dp를 구성한 것이다.

파이프 옮기기 2 문제는 시간 제한이 줄고 경우의 수가 많아지는 것으로 봐서 dfs로는 시간초과가 발생할 것 같다는 생각이 든다. 

다음에 다시 풀어봐야지!

 

 

코드

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

public class Main {
	static int N, cnt;
	static int[][] house;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine()); // 집의 크기
		house = new int[N + 1][N + 1];
		// 집의 상태 입력받기
		for (int r = 1; r <= N; r++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int c = 1; c <= N; c++) {
				house[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		cnt = 0;
		DFS(1, 1, 1, 1, 2);
		System.out.println(cnt);
	}

	public static void DFS(int dir, int firstR, int firstC, int secondR, int secondC) {
		// 기저
		if (secondR == N && secondC == N) {
			cnt++;
			return;
		}
		// 유도
		if (dir == 1) { // 파이프가 가로로 있는 경우
			// -> 이동 가능한 경우
			if (inRange(secondR, secondC + 1) && house[secondR][secondC + 1] == 0) {
				DFS(1, firstR, firstC + 1, secondR, secondC + 1);
			}
			// 대각선 아래 이동 가능한 경우
			if (inRange(secondR + 1, secondC + 1) && house[secondR][secondC + 1] == 0
					&& house[secondR + 1][secondC] == 0 && house[secondR + 1][secondC + 1] == 0) {
				DFS(3, firstR, firstC + 1, secondR + 1, secondC + 1);
			}
		} else if (dir == 2) { // 세로
			// 아래 이동 가능한 경우
			if (inRange(secondR + 1, secondC) && house[secondR + 1][secondC] == 0) {
				DFS(2, firstR + 1, firstC, secondR + 1, secondC);
			}
			// 대각선 아래 이동 가능한 경우
			if (inRange(secondR + 1, secondC + 1) && house[secondR][secondC + 1] == 0
					&& house[secondR + 1][secondC] == 0 && house[secondR + 1][secondC + 1] == 0) {
				DFS(3, firstR + 1, firstC, secondR + 1, secondC + 1);
			}
		} else { // 대각선
			// 가로로 이동 가능한 경우
			if (inRange(secondR, secondC + 1) && house[secondR][secondC + 1] == 0) {
				DFS(1, firstR + 1, firstC + 1, secondR, secondC + 1);
			}
			// 세로로 이동 가능한 경우
			if (inRange(secondR + 1, secondC) && house[secondR + 1][secondC] == 0) {
				DFS(2, firstR + 1, firstC + 1, secondR + 1, secondC);
			}
			// 대각선 아래 이동 가능한 경우
			if (inRange(secondR + 1, secondC + 1) && house[secondR][secondC + 1] == 0
					&& house[secondR + 1][secondC] == 0 && house[secondR + 1][secondC + 1] == 0) {
				DFS(3, firstR + 1, firstC + 1, secondR + 1, secondC + 1);
			}
		}
	}

	public static boolean inRange(int R, int C) {
		return R >= 1 && R <= N && C >= 1 && C <= N;
	}
}

 

참고 자료