17070번 - 파이프 옮기기

골드 4티어 파이프옮기기 라는 문제이다.
각 자세별로 아래와 같이 이동 가능하고 각 파이프가 차지하는 칸은 색칠한 곳과 같다.

이때 파이프가 이동 할 수 있는 경로의 경우의 수를 구하는 문제이다.

입출력은 아래와 같으며 파이프는 좌측 상단 두칸에 가로로 출발한다.

1이 포함된 칸은 이용하지 못한다.

그렇다면 조건은 아래와 같다는 것을 알 수 있다.

 

1. 파이프의 끝이 우측 하단에 도달하면 경우의 수 + 1이다.

2. 다음에 이동할 칸이 1이면 안된다.

3. 가로로 이동할 때(가로 또는 대각선) x 좌표만 +1이 된다.(x좌표는 N보다 작아야 함)

4. 세로로 이동할 때(세로 또는 대각선)는 y 좌표만 -1이 된다.(y좌표는 0보다 커야 함)

5. 가로 세로 대각선 모두 대각선으로 이동 가능하다.
    하지만 대각선으로 이동할 시 (x+1, y)과 (x, y-1)이 1이 아닌지 고려해야 한다.

 

이런 방식으로 코드를 작성하면 다음과 같다.

import java.io.*;

public class Main {

    static int N;
    static int[][] house;
    static int count = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        house = new int[N][N];

        for (int y = N-1; y >= 0; y--) {// 파이프는 시작시(0, N-1), (1, N-1)에 존재
            String line = br.readLine();
            String[] numbers = line.split("\\s+"); // 하나 이상의 공백을 기준으로 분리
            for (int x = 0; x < N; x++) {
                house[y][x] = Integer.parseInt(numbers[x]);
            }
        }

        recursion(N-1, 1, 0);

        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
    }

    static void recursion(int y, int x, int type) {
        if (y == 0 && x == N-1) {
            count++;
            return;
        }
        if (type == 0 || type == 2) { // 가로 또는 대각
            if (x + 1 < N && house[y][x + 1] == 0) {
                recursion(y, x + 1, 0);
            }
        }
        if (type == 1 || type == 2) { // 세로 또는 대각
            if (y - 1 >= 0 && house[y - 1][x] == 0) {
                recursion(y - 1, x, 1);
            }
        }
        if (x + 1 < N && y - 1 >= 0 && house[y - 1][x] == 0 && house[y][x + 1] == 0 && house[y - 1][x + 1] == 0) {
            recursion(y - 1, x + 1, 2);
        }
    }
}

 

 

이렇듯 쉽게 푼것 같지만, 비슷한 방식으로 시도했을 때, 틀렸다는 결과가 나왔다.

이동 전에 검사하는 것이 아닌 이동 후에 검사하는 방식으로 코드를 짰다.

import java.io.*;

public class Main {

    static int N;
    static int[][] house;
    static int count = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        house = new int[N][N];

        for (int y = N-1; y >= 0; y--) {// 파이프는 시작시(0, N-1), (1, N-1)에 존재
            String line = br.readLine();
            String[] numbers = line.split("\\s+"); // 하나 이상의 공백을 기준으로 분리
            for (int x = 0; x < N; x++) {
                house[y][x] = Integer.parseInt(numbers[x]);
            }
        }

        recursion(N-1, 1, 0);

        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
    }

    static void recursion(int y, int x, int type) {
        if (y == 0 && x == N-1) {
            count++;
            return;
        }
        if (y < 0 || x > N-1) {
            return;
        }
        if (house[y][x] == 1) {
            return;
        }
        if(type == 0) { // 가로
            recursion(y, x+1, 0);
            recursion(y-1, x+1, 2);
        } else if(type == 1) { // 세로
            recursion(y-1, x, 1);
            recursion(y-1, x+1, 2);
        } else { // 대각
            if (house[y][x-1] == 1 || house[y+1][x] == 1) {
                return;
            }
            recursion(y, x+1, 0);
            recursion(y-1, x, 1);
            recursion(y-1, x+1, 2);
        }
    }
}

 

블로그를 쓰며 찾아낸 것인데, 만일 이렇게 된다면 마지막 칸이 1이거나, 대각선 조건을 만족하지 않을 때,

미리 검사를 하고 넘기는 과정과는 다르게, 경우의 수에 1이 추가된다.

정말 심각한 오류이다 ㄷㄷ,,

 

이렇듯 글을 쓰며 오류를 찾아 낼 수도 있다. 앞으로도 꾸준하게 알고리즘 풀이를 작성해야겠다.