BOJ_17070_파이프 옮기기1

#dfs #dp

DFS를 사용한 풀이

DFS를 활용한 재귀로 완전탐색을 하기
가로 -> 가로, 대각선
세로 -> 세로, 대각선
대각선 -> 전부 가능

갈 수 있는 방향으로 한 칸씩 이동하면서 끝에 도달하면 카운트 해주기

void DFS(int r, int c, int dir){
 
    if(r==N && c==N){
        answer++;
        return;
    }
 
    for(int i = 0; i<3; i++){
        //가로->세로 or 세로->가로 안됨
        if((dir==0 && i==1) || (dir==1 && i==0)) continue;
 
        int nr = r + dr[i];
        int nc = c + dc[i];
        if(chk(nr,nc)==false) continue;     //범위 벗어나거나 벽이면 
        if(i==2 && (map[r+1][c]==1 || map[r][c+1]==1)) continue;
        //대각선인데 나머지 칸이 벽이면 
        DFS(nr, nc, i);
 
    }
}

DP를 활용한 풀이

dfs보단 접근을 생각해내기 어렵지만 효율적으로 풀 수 있다

현재 확인 중인 arr[i][j] 로 도달할 때 이전 칸에서 가로, 세로, 대각선 어디서 오는지 확인한다
대각선인 경우 세 칸이 모두 0인지 확인(지문에 써있는 조건)

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

public class Main {


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int size = Integer.parseInt(br.readLine());

        int[][] wall = new int[size + 1][size + 1];
        // 가로, 세로, 대각선 각각에 이차원 배열을 사용하기 위함
        int[][][] dp = new int[size + 1][size + 1][3];

        for (int x = 1; x <= size; x++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int y = 1; y <= size; y++) {
                wall[x][y] = Integer.parseInt(st.nextToken());
            }
        }


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

        for (int x = 1; x <= size; x++) {
            for (int y = 1; y <= size; y++) {

                if(wall[x][y]==1)
                    continue;

                dp[x][y][0] += dp[x][y - 1][0] + dp[x][y - 1][2];
                dp[x][y][1] += dp[x - 1][y][1] + dp[x - 1][y][2];

                if (wall[x - 1][y] == 0 && wall[x][y - 1] == 0) {
                    dp[x][y][2] += dp[x - 1][y - 1][0] + dp[x - 1][y - 1][1] + dp[x - 1][y - 1][2];
                }

            }
        }

        System.out.println(dp[size][size][0] + dp[size][size][1] + dp[size][size][2]);

        br.close();


    }

}