[JAVA] [DP] [DFS] 17070. 파이프 옮기기 1

17070. 파이프 옮기기 1

17070번: 파이프 옮기기 1

 

 

• 내 풀이 - dfs
  • 대각선일때 세로, 가로 따로 계산하는걸 처음에 if문을 한번에 합쳐서 오류가 남
  • 대각선은 범위 3칸 차지하는것 주의

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

public class Main {
    static int n,result;
    static int[][] home;

    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        result=0;

        home= new int[n+1][n+1];
        for (int i = 1; i < n+1; i++) {
            st=new StringTokenizer(br.readLine());
            for (int j = 1; j < n+1; j++) {
                home[i][j]= Integer.parseInt(st.nextToken());
            }
        }
        dfs(0,1,2);
        System.out.println(result);

    }
    private static void dfs(int line, int r, int c){
        if (r==n && c==n){
            result++;
            return;
        }

        switch (line){ // 가로 0, 세로1, 대각선2
            case 0:
                if (c+1<=n && home[r][c+1]==0){
                    dfs(0, r, c+1); // 가로
                }
                break;
            case 1:
                if (r+1<=n && home[r+1][c]==0){
                    dfs(1, r+1, c);
                }
                break;
            case 2:
                if (c+1<=n && home[r][c+1]==0) {
                    dfs(0, r, c + 1);
                }
                if (r+1<=n&& home[r+1][c]==0){
                    dfs(1, r+1,c);
                }
                break;
        }
        if (r+1<=n && c+1<=n && home[r+1][c+1]==0 && home[r][c+1]==0 && home[r+1][c]==0){
            dfs(2, r+1, c+1); //대각선은 무조건 실행
        }
    }
}

 

• 다른 사람 풀이 - DP
  • dp[ i ][ j ][ n ] -> n =0 : 가로, n=1 : 세로, n=2: 대각선
  • 현재 위치에 가로방향으로 온 경우 -> 이전: 가로, 대각선 
  • 현재 위치에 세로방향으로 온 경우 -> 이전: 세로, 대각선
  • 현재 위치에 대각선으로 온 경우 -> 이전: 가로, 세로, 대가선
    • 대각선인 경우: 범위 3칸 모두 벽지가 없어야함

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

public class JUN17070_leenamgon {
	
	static int n;
	static int[][] board;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		board = new int[n + 1][n + 1];
		int[][][] dp = new int[n + 1][n + 1][3];
		dp[1][2][1] = 1;
		
		for (int i = 1; i < n + 1; i ++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j < n + 1; j ++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				
				if (board[i][j] == 0) {
					dp[i][j][0] += dp[i - 1][j][0] + dp[i - 1][j][2];
					dp[i][j][1] += dp[i][j - 1][1] + dp[i][j - 1][2];
					if (board[i][j - 1] == 0 && board[i - 1][j] == 0) {
						dp[i][j][2] += dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];
					}
				}
			}
		}

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

}

 

- 3차원 배열

원래는 앞에가 3이 오는게 맞음

dp [ 3 ] [ n+1 ] [ n+1 ] -> 2차원 배열이 3개