[BOJ] 17070번 파이프 옮기기1 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    static int n;
    static int[][] map, dp;

    public static void main(String[] args) throws IOException {
        init();
        dfs(0, 1, 0);
        print();
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        dp = new int[n][n];
        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    /**
     * @param r         파이프 앞부분의 현재 행
     * @param c         파이프 앞부분의 현재 열
     * @param direction 가로 = 0, 세로 = 1, 대각선 = 2
     */
    private static void dfs(int r, int c, int direction) {
        if (isOutOfRange(r, c) || isWall(r, c)) {
            return;
        }

        if (direction == 0) {
            dfs(r, c + 1, direction);
            dfs(r + 1, c + 1, 2);
        } else if (direction == 1) {
            dfs(r + 1, c, direction);
            dfs(r + 1, c + 1, 2);
        } else {
            if (isWall(r - 1, c) || isWall(r, c - 1)) {
                return;
            }
            dfs(r, c + 1, 0);
            dfs(r + 1, c, 1);
            dfs(r + 1, c + 1, direction);
        }
        dp[r][c]++;
    }

    private static boolean isOutOfRange(int r, int c) {
        return r == n || c == n;
    }

    private static boolean isWall(int r, int c) {
        return map[r][c] == 1;
    }

    private static void print() {
        System.out.println(dp[n - 1][n - 1]);
    }
}

📄 해설

접근

• DP 나 DFS 로 풀 수 있는 문제. DP 로 접근을 하다가 도저히 못하겠어서 DFS 로 풀었더니 간단하게 풀린 문제.
• 격자의 상태를 저장할 배열과, 각 칸으로 이동가능한 경우의 수를 저장할 배열 두개를 사용한다.
• 이후에는 문제의 조건에 충실히 구현하면 된다.
  1. 가로, 세로, 대각선의 방향이 존재한다.
  2. 가로, 세로, 대각선일 경우 각각의 가능한 다음위치를 고려해본다.
  3. 가로, 세로, 대각선일 경우 각각의 빈 칸이어야 하는 곳을 고려해본다.

과정

• 입력을 받고, DFS 를 수행
• 기저조건(종료조건)으로는 위치가 범위를 벗어나는지, 해당 위치가 벽인지를 체크한다. (첫번째 if-else문)
• 이후 방향에 따라 각각의 다음 위치, 방향의 경우의 수로 가지를 뻗는다. (두번째 if-else문)
  • 가로, 세로는 2가지 -> 2개의 DFS 호출
  • 대각선은 3가지 -> 3개의 DFS 호출
  • 대각선일 경우, 현 위치 기준으로 왼쪽과 위쪽이 벽인지 추가로 체크한다.
• 현재 위치로 올 수 있는 경우의 수를 증가시킨다. (dp[r][c]++;)