[BJ] 17070_파이프옮기기1

BJ 17070 파이프옮기기1

 

 

문제링크

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

17070번: 파이프 옮기기 1

 

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/mlzigFZAoAI

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l5;

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


public class BJ_G5_17070_파이프옮기기1 {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder output = new StringBuilder();
    private static StringTokenizer tokens;

    static int N;
    static int[][] map;

    static int HOR = 0, VER = 1, DIA = 2;
    static int C;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(instr));
        N = Integer.parseInt(input.readLine());
        map = new int[N][N];
        for (int r = 0; r < N; r++) {
            tokens = new StringTokenizer(input.readLine());
            for (int c = 0; c < N; c++) {
                map[r][c] = Integer.parseInt(tokens.nextToken());
            }
        }

        // for (int[] row : map) {
        //     System.out.println(Arrays.toString(row));
        // }

        dfs(0, 1, HOR);

        System.out.println(C);
    }

    static void dfs(int r, int c, int d) {
        // base part
        if (r == N - 1 && c == N - 1) {
            C++;
            return;
        }
        // inductive part
        // 수평--> 수평 or 대각, 수직 --> 수직 or 대각, 대각 --> 수평, 수직, 대각
        // 대각은 언제나 가능, 가로로는? 수평이나 대각이었다면 가능 --> 수직이 아니면 OK!!, 수직으로는? 수직이나 대각이면 가능 --> 수평만 아니면 OK!
        int nr = r + 1;
        int nc = c + 1;
        if (canGo(nr, nc, true)) {
            dfs(nr, nc, DIA);
        }
        // 수직이 아니면 --> 수평 가능
        if (d != VER) {
            nr = r;
            nc = c + 1;
            if (canGo(nr, nc, false)) {
                dfs(nr, nc, HOR);
            }
        }
        // 수평이 아니면 --> 수직 가능
        if (d != HOR) {
            nr = r + 1;
            nc = c;
            if (canGo(nr, nc, false)) {
                dfs(nr, nc, VER);
            }
        }
    }

    static boolean canGo(int r, int c, boolean isDia) {
        if (r >= N || c >= N) {
            return false;
        }
        if (map[r][c] == 1) {
            return false;
        }
        if (isDia && (map[r - 1][c] == 1 || map[r][c - 1] == 1)) {
            return false;
        }
        return true;
    }

    // REMOVE_START
    private static String instr = "6\r\n" +
                                  "0 0 0 0 0 0\r\n" +
                                  "0 1 0 0 0 0\r\n" +
                                  "0 0 0 0 0 0\r\n" +
                                  "0 0 0 0 0 0\r\n" +
                                  "0 0 0 0 0 0\r\n" +
                                  "0 0 0 0 0 0";
    // REMOVE_END
}