BOJ_17070 : 파이프 옮기기 1

👉 문제링크

17070번: 파이프 옮기기 1

---

---

🔸 문제 분석 🔸

• N x N 격자공간에서 좌상단부터 우상단으로 파이프를 이동시킬 수 있는 경우의 수를 출력한다.
  • 파이프는 오른쪽, 우하단 대각선, 아래로 밀 수 있다.
  • 격자공간에는 돌이 있다.
  • 파이프를 돌릴 때 확보되어야 하는 공간에 돌이 있거나 격자 공간을 벗어나서는 안된다.
• DFS로 끝까지 도착하는 경우를 카운트한다.
  • 기존 가로 일때는 가로와 대각선, 기존 세로 일때는 세로와 대각선, 기존 대각선 일때는 세 가지 모든 경우를 확인해야 한다.

🔸 코드 🔸

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

public class Main {
    private static int N, map[][], ans;
    private static int[] dr = {0,1,1};
    private static int[] dc = {1,1,0};
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

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

        // DFS
        ans = 0;
        dfs(0, 1, 0);

        // Output
        System.out.println(ans);
    }

    private static void dfs(int r, int c, int d) {
        if (r == N-1 && c == N-1) {
            ans++;
            return;
        }

        switch (d) {
            case 0: // 기존 가로
                // 가로
                if (check(r+dr[0],c+dc[0]))
                    dfs(r+dr[0], c+dc[0], 0);
                // 대각선
                if (check(r+dr[0],c+dc[0])
                        &&check(r+dr[1],c+dc[1])
                        &&check(r+dr[2],c+dc[2]))
                    dfs(r+dr[1], c+dc[1], 1);
                break;
            case 1: // 기존 대각선
                // 대각선
                if (check(r+dr[0],c+dc[0])
                        &&check(r+dr[1],c+dc[1])
                        &&check(r+dr[2],c+dc[2]))
                    dfs(r+dr[1], c+dc[1], 1);
                // 가로
                if (check(r+dr[0],c+dc[0]))
                    dfs(r+dr[0], c+dc[0], 0);
                // 세로
                if (check(r+dr[2],c+dc[2]))
                    dfs(r+dr[2], c+dc[2], 2);
                break;
            case 2: // 기존 세로
                // 세로
                if (check(r+dr[2],c+dc[2]))
                    dfs(r+dr[2], c+dc[2], 2);
                // 대각선
                if (check(r+dr[0],c+dc[0])
                        &&check(r+dr[1],c+dc[1])
                        &&check(r+dr[2],c+dc[2]))
                    dfs(r+dr[1], c+dc[1], 1);
                break;
        }
    }

    private static boolean check(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < N && map[r][c] == 0)
            return true;
        return false;
    }
}

🔸 코드 해석 🔸

• 파이프의 앞쪽 입구의 좌표는 0, 1부터 시작한다.
• 파이프 좌표를 r, c 로, 방향을 d로 넘겨 dfs 메서드에서 재귀를 수행한다.
  • 각 방향에 따른 확인해야 할 경우의 수로 재귀 호출을 수행한다.
  • 빈공간 확인은 따로 check 메서드를 빼서 확인한다.
  • 끝까지 도착하면 ans를 +1 한다.
• ans를 출력한다.

---

🔸 end 🔸

• dfs로 풀이했지만, DP로 더 효율적이게 풀이가 가능한 것 같다.