[BOJ] 17070 : 파이프 옮기기 1(Java)

문제 링크

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

17070번: 파이프 옮기기 1

---

💡 풀이

파이프를 옮겨가며 끝 점에 도달 할 수 있는 모든 경우의 수를 구하는 문제이기 때문에, DFS를 사용해 풀이했습니다.

또한, 길이가 2인 파이프는 파이프의 끝 점에 따라 시작점이 따라 오는 구조이기 때문에 파이프 끝 점(두 번째 점)만을 이용해 풀이했습니다. 

 

먼저, 움직일 수 있는 경우의 수를 선언해줍니다. 여기서는 가로, 세로, 대각선 방향으로 움직일 수 있기 때문에 다음과 같이 선언합니다. 하지만, 각 파이프 모양마다 움직일 수 있는 방향이 정해져 있기 때문에 추후에 별도의 조건식이 필요합니다.

static int[][] move = {
        {0, 1}, // 가로
        {1, 0}, // 세로
        {1, 1}  // 대각선
};

 

DFS

DFS 함수에서 먼저 함수가 종료되는 조건인 Base Case를 살펴보겠습니다.

Base Case

함수가 종료되는 조건은 두 가지 입니다. 

1. 파이프가 끝에 도달한 경우
2. 파이프가 그래프의 범위를 벗어난 경우

위 두 가지에 대한 조건을 명시해 줍시다. (저는 그래프의 시작과 끝을 0 ~ (N - 1)로 설정했습니다.)

// Base Case
if (y >= N && x >= N) return;
if (y == N - 1 && x == N - 1) {
    answer++;
    return;
}

Recursive Case

다음은 DFS가 동작하는 부분입니다.

move 배열을 하나씩 돌며 재귀를 수행합니다. 여기서 주의할 점은 파이프이 모양이 가로인 경우 세로 방향으로 갈 수 없고, 모양이 세로인 경우 가로 방향으로 갈 수 없습니다. 따라서 이에 따른 조건을 추가해 주어야 합니다. 

또한, 파이프의 모양이 대각선인 경우, 끝 점의 왼 쪽과 위 쪽이 비어있어야 하기 때문에 이에 대한 검사도 필요합니다. 

 // Recursive Case
/*
type : 현재 파이프의 모양
type = 0 : 가로
type = 1 : 세로
type = 2 : 대각선
 */
for (int cand = 0; cand < 3; cand++) {
    // 파이프가 가로인 경우, 세로로 이동 할 수 없다.
    if(type == 0 && cand == 1) continue;
    // 파이프가 세로인 경우, 가로로 이동 할 수 없다.
    if(type == 1 && cand == 0) continue;

    int dy = y + move[cand][0];
    int dx = x + move[cand][1];

    if(isOutOfBound(dy, dx)) continue;
    if(graph[dy][dx] == 1) continue;
    // 대각선 방향일 경우, 추가적인 왼쪽과 위 공간의 확인이 필요
    if(cand == 2 && !isEmptySpace(dy, dx)) continue;

    recur(dy, dx, cand);
}

전체 코드

전체적인 코드는 다음과 같습니다. 

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

public class Q17070 {
    static int N, answer;
    static int[][] graph;
    static int[][] move = {
            {0, 1}, // 가로
            {1, 0}, // 세로
            {1, 1}  // 대각선
    };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        graph = new int[N][N];
        for (int y = 0; y < N; y++) {
            st = new StringTokenizer(br.readLine());
            for (int x = 0; x < N; x++) {
                graph[y][x] = Integer.parseInt(st.nextToken());
            }
        }

        answer = 0;
        recur(0, 1, 0);
        System.out.println(answer);
    }

    static void recur(int y, int x, int type) {
        // Base Case
        if (y >= N && x >= N) return;
        if (y == N - 1 && x == N - 1) {
            answer++;
            return;
        }

        // Recursive Case
        /*
        type : 현재 파이프의 모양
        type = 0 : 가로
        type = 1 : 세로
        type = 2 : 대각선
         */
        for (int cand = 0; cand < 3; cand++) {
            // 파이프가 가로인 경우, 세로로 이동 할 수 없다.
            if(type == 0 && cand == 1) continue;
            // 파이프가 세로인 경우, 가로로 이동 할 수 없다.
            if(type == 1 && cand == 0) continue;

            int dy = y + move[cand][0];
            int dx = x + move[cand][1];

            if(isOutOfBound(dy, dx)) continue;
            if(graph[dy][dx] == 1) continue;
            // 대각선 방향일 경우, 추가적인 왼쪽과 위 공간의 확인이 필요
            if(cand == 2 && !isEmptySpace(dy, dx)) continue;

            recur(dy, dx, cand);
        }
    }

    static boolean isOutOfBound(int y, int x) {
        return y < 0 || x < 0 || y >= N || x >= N;
    }

    static boolean isEmptySpace(int y, int x) {
        return graph[y][x - 1] == 0 && graph[y - 1][x] == 0;
    }
}