[BOJ] 17070.파이프 옮기기 1(DFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

이 문제도 사실 

주어진 조건대로만 잘 구현하면 되는 DSF 문제다.

1. 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.

- 파이프를 옮기기 위한 다음 좌표가 벽이라면 pass 해주자.

2. 파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향

3. 파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 

   대각선 방향으로 놓여진 경우에는 3가지

- 파이프가 놓여져있는 상황에 맞게 파이프를 이동시켜보자.

4. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수 구하기

- 도착지에 도달하면 방법을 count 해주자.

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ17070 {
 
    static int N, res, map[][];
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        // 집 상태 입력
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        // 파이프를 밀어보자.
        // 가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지
        push(0, 1, 0);
 
        System.out.println(res);
    }
 
    /**
     * 파이프 밀기
     * @param x    행 좌표
     * @param y    열 좌표
     * @param nd    0: 가로, 1: 세로, 2: 우하대각선
     */
    private static void push(int x, int y, int nd) {
 
        // 도착지에 도달
        if(x == N - 1 && y == N - 1) {
            res++;
            return;
        }
        
        // 파이프가 가로로 놓여진 경우
        if(nd == 0) {
            // 범위를 넘지 않고, 벽이 없을 경우 우로 이동하거나
            if(y + 1 < N && map[x][y + 1] == 0)
                push(x, y + 1, 0);
            
            // 범위를 넘지 않고, 벽이 없을 경우 우하대각선으로 이동하거나
            if(x + 1 < N && y + 1 < N) {
                if(map[x+1][y] == 0 && map[x+1][y+1] == 0 && map[x][y+1] == 0)
                    push(x + 1, y + 1, 2);
            }
        }
        // 파이프가 세로로 놓여진 경우
        else if(nd == 1) {
            // 범위를 넘지 않고, 벽이 없을 경우 하로 이동하거나
            if(x + 1 < N && map[x+1][y] == 0)
                push(x + 1, y, 1);
            // 범위를 넘지 않고, 벽이 없을 경우 우하대각선으로 이동하거나
            if(x + 1 < N && y + 1 < N) {
                if(map[x+1][y] == 0 && map[x+1][y+1] == 0 && map[x][y+1] == 0)
                    push(x + 1, y + 1, 2);
            }
        }
        // 파이프가 우하대각선으로 놓여진 경우
        else if(nd == 2) {
            // 범위를 넘지 않고, 벽이 없을 경우 우로 이동하거나
            if(y + 1 < N && map[x][y + 1] == 0)
                push(x, y + 1, 0);
            // 범위를 넘지 않고, 벽이 없을 경우 하로 이동하거나
            if(x + 1 < N && map[x+1][y] == 0)
                push(x + 1, y, 1);            
            // 범위를 넘지 않고, 벽이 없을 경우 우하대각선으로 이동하거나
            if(x + 1 < N && y + 1 < N) {
                if(map[x+1][y] == 0 && map[x+1][y+1] == 0 && map[x][y+1] == 0)
                    push(x + 1, y + 1, 2);
            }        
    
        }
 
    }
 
}
 

#. Code_v2

'주어진 조건대로만' 잘 구현하다보니 중복코드가 많아져서

Version2 로 약간 수정해보았다.

위 코드에서는 "현재 놓인 파이프의 방향"이 기준이었다면,

아래 코드는 "다음에 놓을 파이프의 방향"이 기준이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ17070_v2 {
 
    static int N, res, map[][];
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        // 집 상태 입력
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        // 파이프를 밀어보자.
        // 가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지
        push(0, 1, 0);
 
        System.out.println(res);
    }
 
    /**
     * 파이프 밀기
     * 
     * @param x  행 좌표
     * @param y  열 좌표
     * @param nd 0: 가로, 1: 세로, 2: 우하대각선
     */
    private static void push(int x, int y, int nd) {
 
        // 도착지에 도달
        if (x == N - 1 && y == N - 1) {
            res++;
            return;
        }
 
        // 파이프가 가로로 놓이기 위해서
        // 파이프가 현재 가로이거나 우하대각선일 경우
        if (nd == 0 || nd == 2) {
            // 범위를 넘지 않고, 벽이 없을 경우 가로로 이동
            if (y + 1 < N && map[x][y + 1] == 0)
                push(x, y + 1, 0);
        }
 
        // 파이프가 세로로 놓이기 위해서
        // 파이프가 현재 세로이거나 우하대각선일 경우
        if (nd == 1 || nd == 2) {
            // 범위를 넘지 않고, 벽이 없을 경우 세로로 이동
            if (x + 1 < N && map[x + 1][y] == 0)
                push(x + 1, y, 1);
        }
 
        // 파이프가 우하대각선으로 놓이는 경우는 모든 경우
        // 범위를 넘지 않고, 벽이 없을 경우 우하대각선으로 이동하거나
        if (x + 1 < N && y + 1 < N && 
                map[x + 1][y] == 0 && map[x + 1][y + 1] == 0 && map[x][y + 1] == 0) {
            push(x + 1, y + 1, 2);
        }
    }
 
}