[ 백준 ] 17070 파이프 옮기기 1

Link | 17070번 문제 : 파이프 옮기기 1

Solution

처음에 BFS로 문제를 해결하였다가 시간초과가 발생하여 DP로 해결하였다.

다음과 같은 집이 있다고 가정하자.

각각의 영역을 타일이라고 칭하고 타일은 3개의 값 h, v, d를 가진다.

class Tile {

    int h, v, d;

    public Tile(int h, int v, int d) {
        this.h = h;
        this.v = v;
        this.d = d;
    }

    public void setHVD(int h, int v, int d) {
        this.h = h;
        this.v = v;
        this.d = d;
    }

    public int total() {
        return h + v + d;
    }
}

각각의 값은 pipe의 한 쪽이 해당 타일에 위치 시킬 수 있는 방법의 수이다.

h는 pipe가 horizontal로 위치하고 오른쪽이 타일에 위치하는 경우이다.

v는 pipe가 vertical로 위치하고 아래쪽이 타일에 위치하는 경우이다.

d는 pipe가 diagonal로 위치하고 우측하단쪽이 타일에 위치하는 경우이다.

이 때 점화식은 다음과 같다.

T_h = H_h + H_d
T_v = V_v + V_d
T_d = D_h + D_v + D_d

다만 점화식을 실행할 때 현재 Tile(빨간색)에 벽이 있는지를 우선 확인한다.

또한 T_d를 구할 때는 현재 Tile의 위아래에 벽이 있는지도 확인한다.

타일의 좌표가 1 부터 N까지 2차원으로 존재할 때 다음과 같이 점화식을 실행한다.

walls 값이 true이면 벽이 있는 것이다.

private static void dp() {
    for (int r = 1; r <= SIZE; r++) {
        for (int c = 3; c <= SIZE; c++) {
            if (!walls[r][c]) {
                Tile tileH = tiles[r][c - 1];
                Tile tileV = tiles[r - 1][c];
                Tile tileD = tiles[r - 1][c - 1];
                tiles[r][c].setHVD(tileH.h + tileH.d, tileV.v + tileV.d,
                        walls[r - 1][c] || walls[r][c - 1] ? 0 : tileD.total());
            }
        }
    }
}

이때 c(column) 값이 3부터 시작하는 것을 확인할 수 있는데 이는 c가 1 or 2 일 때 Tile의 h, v, d의 값이 무조건 0이기 때문이다.

아래의 그림은 최초 pipe 상태이며 회색 타일은 c = 1 or 2로 점화식에서 제외해도 되는 영역이다.

Example

다음을 예시로 하며 회색 tile은 벽이다.

이를 h, v, d로 나타내면 빨간 타일의 h만 1이고 나머지 모든 타일은 0이다.

빨간색 타일은 현재 탐색하고자하는 타일 T이며 왼쪽은 H, 위쪽은 V, 대각선은 D 타일이다.

공간을 벗어난 곳에는 가상의 타일이 존재한다고 생각하고 가상의 타일은 h, v, d 값이 모두 0이다.

회색 블럭은 벽이 있기 때문에 탐색하지 않는다.

최종적으로 N N에 pipe가 위치하는 경우의 수는 N N 위치에 있는 타일의 h + v + d 이다.

예시에서는 1이다.

Code

Github Repository

private static int SIZE;
private static boolean[][] walls;
private static Tile[][] tiles;

private static void solution() throws IOException {
    init();
    read();
    dp();
    result.append(tiles[SIZE][SIZE].total());
}

private static void init() throws IOException {
    SIZE = Integer.parseInt(reader.readLine());
    walls = new boolean[SIZE + 1][SIZE + 1];
    tiles = new Tile[SIZE + 1][SIZE + 1];
}

private static void read() throws IOException {
    StringTokenizer tokenizer;
    IntStream.rangeClosed(2, SIZE).forEach(col -> tiles[0][col] = new Tile(0, 0, 0));
    for (int r = 1; r <= SIZE; r++) {
        tokenizer = new StringTokenizer(reader.readLine());
        for (int c = 1; c <= SIZE; c++) {
            walls[r][c] = Integer.parseInt(tokenizer.nextToken()) == 1;
            tiles[r][c] = new Tile(0, 0, 0);
        }
    }
    tiles[1][2].setHVD(1, 0, 0);
}

private static void dp() {
    for (int r = 1; r <= SIZE; r++) {
        for (int c = 3; c <= SIZE; c++) {
            if (!walls[r][c]) {
                Tile tileH = tiles[r][c - 1];
                Tile tileV = tiles[r - 1][c];
                tiles[r][c].setHVD(tileH.h + tileH.d, tileV.v + tileV.d,
                        walls[r - 1][c] || walls[r][c - 1] ? 
                                0 : tiles[r - 1][c - 1].total());
            }
        }
    }
}

static class Tile {

    int h, v, d;

    public Tile(int h, int v, int d) {
        this.h = h;
        this.v = v;
        this.d = d;
    }

    public void setHVD(int h, int v, int d) {
        this.h = h;
        this.v = v;
        this.d = d;
    }

    public int total() {
        return h + v + d;
    }
}