[백준] 17070. 파이프 옮기기 - Java

🖇️ 문제 링크

17070번: 파이프 옮기기 1

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다.

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

 

---

💡 문제 분석

💡

dfs(y, x, d) = 현재 파이프가 (y, x) 위치이고 방향이 d일 때 목표 지점에 갈 수 있는 경우의 수

파이프의 위치와 방향에 따라 경우의 수를 계산하며, 다이내믹 프로그래밍을 진행합니다.

 

---

⌨️ 코드

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

public class Q17070 {
    static int N;
    static int[][] map;
    static int[][][] cache;
    static int[] dy = {0, 1, 1}, dx = {1, 1, 0};

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];
        cache = new int[N][N][3];


        for(int r = 0; r < N; r++)
            for(int c = 0; c < N; c++) {
                map[r][c] = sc.nextInt();
                Arrays.fill(cache[r][c], -1);
            }

        System.out.println(dfs(0, 1, 0));
    }

    public static int dfs(int y, int x, int d) {
        if(y < 0 || x < 0 || y >= N || x >= N || map[y][x] == 1)
            return 0;
        // 대각선 이동할 때, 빈칸이어어야 하는 곳
        if(d == 1 && (map[y - 1][x] == 1 || map[y][x - 1] == 1))
            return 0;

        if(y == N - 1 && x == N - 1)
            return 1;

        int ret = cache[y][x][d];
        if(ret != -1)
            return ret;

        ret = 0;
        for(int dir = 0; dir < 3; dir++) {
            int ny = y + dy[dir], nx = x + dx[dir];
            // 가로 -> 세로, 세로 -> 가로 불가능
            if((d == 0 && dir == 2) || (d == 2 && dir == 0))
                continue;
            ret += dfs(ny, nx, dir);
        }

        return cache[y][x][d] = ret;
    }
}

 

---

⏱️ 결과

 

 

 

Uploaded by Notion2Tistory v1.1.0