[백준] 17070. 파이프 옮기기 1(Java)

문제

17070번: 파이프 옮기기 1

풀이

시작점(1, 2)에서 종료점(N, N)까지 갈 수 있는 방법을 구하는 문제

BFS, DFS, DP 등 다양하게 해당 문제를 해결할 수 있는데

DFS 방식과 DP로 해결해보았다.

 

파이프가 '가로'인 경우, 갈 수 있는 방향은 동쪽과 남동쪽

파이프가 '세로'인 경우, 갈 수 있는 방향은 남쪽과 남동쪽

파이프가 '대각'인 경우, 갈 수 있는 방향은 동쪽과 남쪽과 남동쪽이다.

 

이 점을 활용해서 다음으로 갈 방향을 쭉 탐색해주면 된다.

참고로, 대각인 경우에는 현재 위치를 제외한 동쪽과 남쪽 칸에도 영향을 주기 때문에 해당 칸이 벽이 아니어야 한다.

 

이러한 코드를 작성하면 DFS 코드가 완성되고

메모이제이션을 활용하면 탑다운 DP가 된다.

 

재귀를 진행하면서 현재 위치와 방향에 대해, 이미 메모가 되어있다면 메모된 값을 사용하고

메모되지 않았다면 연산의 결과를 메모해준다.

코드(DP)

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

public class Main {
    static int N;
    static int[][] arr;
    static int[][][] dp;
    static int[] dr = {0, 1, 1}; // 우 하 우하
    static int[] dc = {1, 0, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        dp = new int[N][N][3];

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

        System.out.println(recur(0, 1, 0));
    }
    static int recur(int r, int c, int curD){
        if(r >= N || c >= N || arr[r][c] == 1) return 0;

        if(curD == 2 && (arr[r-1][c] == 1 || arr[r][c-1] == 1)) return 0;

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

        if(dp[r][c][curD] > 0) return dp[r][c][curD];

        int ret = 0;

        for(int d = 0 ; d < 3 ; d ++){

            if(curD == 0 && d == 1) continue;
            if(curD == 1 && d == 0) continue;

            int nr = r + dr[d];
            int nc = c + dc[d];

            ret += recur(nr, nc, d);
        }

        return dp[r][c][curD] = ret;
    }
}

코드(DFS)

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

public class Main {
    static int N;
    static int[][] arr;
    static int[] dr = {0, 1, 1}; // 우 하 우하
    static int[] dc = {1, 0, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];

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

        System.out.println(recur(0, 1, 0));
    }
    static int recur(int r, int c, int curD){
        if(r >= N || c >= N || arr[r][c] == 1) return 0;

        if(curD == 2 && (arr[r-1][c] == 1 || arr[r][c-1] == 1)) return 0;

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

        int ret = 0;

        for(int d = 0 ; d < 3 ; d ++){

            if(curD == 0 && d == 1) continue;
            if(curD == 1 && d == 0) continue;

            int nr = r + dr[d];
            int nc = c + dc[d];

            ret += recur(nr, nc, d);
        }

        return ret;
    }
}