[백준] 17069. 파이프 옮기기 2

문제 링크

[백준] 17069. 파이프 옮기기 2

풀이 과정

DFS에 DP를 활용하는 문제입니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
dp = new long[N][N][3];

for (int i = 0; i < N; i++)
    map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

입력으로 최대 32X32 크기의 배열이 주어지므로, Scanner 대신 BufferedReader 를 써야 했습니다.
dp[i][j][k] 는 k 모양으로 (i, j) 좌표에 놓여진 파이프로 한쪽 끝까지 이동시키는 방법의 수를 의미합니다. 예를 들어, dp[0][1][0] 은 가로 모양으로 (0, 1) 에 놓인 파이프가 최대로 이동하여 (N-1, N-1)에 도달하는 모든 경우의 수를 값으로 갖습니다.

for (int i = 0; i < N; i++)
    map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		// map[i] = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

입력은 Stream API를 사용했습니다. Stream 객체를 만드는 과정은 Arrays 클래스의 stream 메소드 를 사용하나, Stream 클래스의 of 메소드 를 사용하나 결과는 같습니다. 입력이 가공되어 int 배열로 변환되는 과정은 다음과 같습니다.

1. 2차원 배열의 입력은 Arrays 클래스의 stream 메소드 를 활용했습니다. 한 줄을 입력 받아, 공백을 기준으로 잘라 배열을 만든 뒤, 만들어진 배열을 stream 메소드의 파라미터로 줘 Stream 객체를 리턴받습니다.
2. 리턴된 Stream 객체로 Stream 클래스의 mapToInt 메소드 를 호출하여 각 요소를 int 타입으로 파싱한 뒤, 이들을 모아 IntStream 객체를 리턴합니다.
3. 리턴된 IntStream 객체를 toArray 메소드 를 통해 int[] 타입으로 변환합니다.

static long dfs(int x, int y, int dir) {
    if (dp[x][y][dir] != 0) return dp[x][y][dir];
    if (x == N - 1 && y == N - 1) return 1;

    for (int d = 0; d < 3; d++) {
        if (dir == HORIZONTAL && d == VERTICAL) continue;
        if (dir == VERTICAL && d == HORIZONTAL) continue;

        int nx = x + dx[d], ny = y + dy[d];

        if (!inRange(nx, ny) || map[nx][ny] == 1) continue;
        if (d == DIAGONAL && (map[nx - 1][ny] == 1 || map[nx][ny - 1] == 1)) continue;

        dp[x][y][dir] += dfs(nx, ny, d);
    }

    return dp[x][y][dir];
}

dfs 메소드 는 각 좌표로부터 끝점에 도달할 수 있는 모든 경우의 개수를 저장하고 리턴합니다. 로직은 파이프 옮기기 1과 비슷하지만, 위 코드는 메모이제이션 된 요소가 있으면 가져다 사용하기 때문에 시간을 단축시킬 수 있습니다.

• if (dp[x][y][dir] != 0) return dp[x][y][dir]; : dir 모양으로 (x, y) 에서 탐색을 한 적이 있으면, dp[x][y][dir] 은 초기 0 값이 아닌 다른 값이 들어 있습니다. 따라서, 0이 아닌 다른 수가 들어가 있으면, 이미 가 본 경로이므로, 재귀를 다시 호출하지 않고 바로 해당 요소를 리턴시킵니다.
• if (x == N - 1 && y == N - 1) return 1; : DFS 탐색을 통해 (N-1, N-1) 에 도달할 수 있으면 1을 리턴시켜, 도달 가능한 방법의 수를 하나 증가시킵니다.
• dp[x][y][dir] += dfs(nx, ny, d); : 다음 번에 위치시킬 수 있는 모든 가능한 파이프 정보로 재귀함수를 각각 호출해, 가능한 가짓수를 가져와 누적시킵니다.
• return dp[x][y][dir]; : 호출 스택 아랫단에 위치한 dfs 메소드들은 갱신된 값을 리턴을 통해 위로 값을 전달합니다.

코드

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

public class Main {
    static int N;
    static int[][] map;
    static long[][][] dp;
    static final int HORIZONTAL = 0, DIAGONAL = 1, VERTICAL = 2;
    static int[] dx = {0, 1, 1}, dy = {1, 1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dp = new long[N][N][3];

        for (int i = 0; i < N; i++)
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        System.out.println(dfs(0, 1, HORIZONTAL));
    }

    static long dfs(int x, int y, int dir) {
        if (dp[x][y][dir] != 0) return dp[x][y][dir];
        if (x == N - 1 && y == N - 1) return 1;

        for (int d = 0; d < 3; d++) {
            if (dir == HORIZONTAL && d == VERTICAL) continue;
            if (dir == VERTICAL && d == HORIZONTAL) continue;

            int nx = x + dx[d], ny = y + dy[d];

            if (!inRange(nx, ny) || map[nx][ny] == 1) continue;
            if (d == DIAGONAL && (map[nx - 1][ny] == 1 || map[nx][ny - 1] == 1)) continue;

            dp[x][y][dir] += dfs(nx, ny, d);
        }

        return dp[x][y][dir];
    }

    static boolean inRange(int x, int y) {
        if (x < 0 || x > N - 1 || y < 0 || y > N - 1) return false;
        return true;
    }
}