[백준] 17070번: 파이프 옮기기 1 - java

문제

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

17070번: 파이프 옮기기 1

 

접근법

처음에 BFS로 풀면 되겠다 싶어 BFS로 풀어 통과를 했다. 그런데 채점현황을 보니 나만 메모리랑 시간이 장난아니게 컸다.. 심지어 처음에는 시간초과가 발생했다. 그래서 알고리즘 분류를 봤더니 DP를 사용하는 문제였다..!ㅋㅋ 두 풀이 다 설명해보겠다.

 

BFS

Pipe 클래스를 하나 만들어 파이프가 시작하는 위치, 파이프의 방향을 변수로 가지도록 하였다. 그냥 BFS 과정처럼 큐에서 꺼낸 파이프가 갈 수 있는 방향은 모두 큐에 담아 큐가 빌 때까지 탐색하였고, 큐에서 꺼낸 파이프의 위치가 (N, N)이면 answer + 1 해주는 방식으로 코드를 작성하였다.

 

주의할 점은 시작할 때 도착 위치 (N, N)이 벽(=1)인 경우를 먼저 체크하지 않으면 시간 초과가 발생한다. 

 

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

public class Main {

    static final int HORIZONTAL = 0;
    static final int DIAGONAL = 1;
    static final int VERTICAL = 2;

    static int N;
    static int[][] home;

    static int[] dirR = {0, 1, 1}; // → ↘︎ ↓
    static int[] dirC = {1, 1, 0}; // → ↘︎ ↓

    static int answer = 0;

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

        N = Integer.parseInt(br.readLine());

        home = new int[N][N];

        for (int r = 0; r < N; r++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                home[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        if (home[N - 1][N - 1] == 1) {
            System.out.println(0);
        } else {
            bfs();
            System.out.println(answer);
        }
    }

    private static void bfs() {
        Deque<Pipe> queue = new ArrayDeque<>();

        // 시작 위치
        queue.offer(new Pipe(0, 0, HORIZONTAL));

        while (!queue.isEmpty()) {
            Pipe now = queue.poll();

            // 도착한 경우
            if (arrive(now)) {
                answer++;
                continue;
            }

            // 다음 파이프의 시작 위치는 현재 파이프의 끝나느 지점이다.
            int nextR = now.r + dirR[now.direction];
            int nextC = now.c + dirC[now.direction];

            switch (now.direction) {
                case HORIZONTAL:
                    for (int i = 0; i < 2; i++) {
                        Pipe next = new Pipe(nextR, nextC, i);
                        if (rangeIn(next)) {
                            queue.offer(next);
                        }
                    }
                    break;
                case VERTICAL:
                    for (int i = 1; i < 3; i++) {
                        Pipe next = new Pipe(nextR, nextC, i);
                        if (rangeIn(next)) {
                            queue.offer(next);
                        }
                    }
                    break;
                case DIAGONAL:
                    for (int i = 0; i < 3; i++) {
                        Pipe next = new Pipe(nextR, nextC, i);
                        if (rangeIn(next)) {
                            queue.offer(next);
                        }
                    }
                    break;
            }
        }
    }

    private static boolean rangeIn(Pipe p) {
        // 세로 방향 확인
        if (p.direction != HORIZONTAL) {
            if (p.r + 1 >= N || home[p.r + 1][p.c] == 1) {
                return false;
            }
        }

        // 가로 방향 확인
        if (p.direction != VERTICAL) {
            if (p.c + 1 >= N || home[p.r][p.c + 1] == 1) {
                return false;
            }
        }

        // 대각선 방향 확인
        if (p.direction == DIAGONAL) {
            if (p.r + 1 >= N || p.c + 1 >= N || home[p.r + 1][p.c + 1] == 1) {
                return false;
            }
        }

        return true;
    }
    private static boolean arrive(Pipe p) {
        int r = p.r + dirR[p.direction];
        int c = p.c + dirC[p.direction];

        return (r == (N - 1) && c == (N - 1));
    }

    static class Pipe {
        // (r, c): 파이프 시작 위치 / direction: 파이프 방향
        int r, c, direction; // 0: 가로 / 1: 세로 / 2: 대각선

        public Pipe(int r, int c, int direction) {
            this.r = r;
            this.c = c;
            this.direction = direction;
        }
    }
}

 

DP

나는 점화식을 아래와 같이 세웠다.

dp[r][c][direction] : (r, c)를 끝점으로 하고, 파이프가 direction 방향일 때의 경우의 수

 

만약 내가 (r, c)를 끝점으로 가지는 가로 방향 파이프라면, (r, c - 1)를 끝점으로 가지는 가로 방향 파이프의 경우의 수와 대각선 방향 파이프의 경우의 수를 더하면 될 것이다.

 

반대로 세로 방향 파이프라면 (r - 1, c)를 끝점으로 가지는 세로 방향 파이프의 경우의 수와 대각선 방향 파이프의 경우의 수를 더하면 될 것이다.

 

대각선 방향의 경우는 어떨지 생각해보자. 문제에서 보여주듯이 가로, 세로, 대각선 방향의 파이프 모두 밀어서 대각선 모양의 파이프를 만들 수 있다. 즉, (r - 1, c - 1)를 끝점으로 가지는 가로, 세로, 대각선 방향 파이프의 경우의 수를 합해주면 된다. 여기서 주의해야 할 것은 (r, c)를 끝점으로 가지는 대각선 파이프를 만들기 위해서는 (r - 1, c) 와 (r, c - 1)가 벽으로 막혀있으면 안된다.

 

이를 바탕으로 코드를 작성하면 아래와 같다. 이 때 벽으로 막힌 경우도 고려해주어야 한다.

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

public class Main {

    static int N;
    static int[][] home;
    static int[][][] dp;

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

        N = Integer.parseInt(br.readLine());

        home = new int[N][N];
        dp = new int[N][N][3];

        for (int r = 0; r < N; r++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                home[r][c] = Integer.parseInt(st.nextToken());
            }
        }

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

        for (int r = 0; r < N; r++) {
            for (int c = 2; c < N; c++) {
                if (home[r][c] == 1) {
                    continue;
                }

                // 가로
                dp[r][c][0] = dp[r][c - 1][0] + dp[r][c - 1][2];

                // 세로
                if (r - 1 >= 0) {
                    dp[r][c][1] = dp[r - 1][c][1] + dp[r - 1][c][2];
                }

                // 대각선
                if (r - 1 >= 0 && home[r][c - 1] == 0 && home[r - 1][c] == 0) {
                    dp[r][c][2] = dp[r - 1][c - 1][0] + dp[r - 1][c - 1][1] + dp[r - 1][c - 1][2];
                }
            }
        }

        System.out.println(dp[N - 1][N - 1][0] + dp[N - 1][N - 1][1] + dp[N - 1][N - 1][2]);
    }
}

 

문제가 그렇게 어렵진 않은데 경우의 수가 복잡해서 애 먹었다...