[BOJ] 17070. 파이프 옮기기 1

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

접근 방법

간단하다. 그냥 재귀 함수를 통해서 현재 상태값과 현재의 위치에서 갈 수 있는 모든 것들을 넣어주

면 된다.

물론 나의 코드는 dp를 사용해서 반복되는 구간을 처리하고 있지 않지만 시간 초과가 일어난다면 DP

를 사용해야 할 것이다. ( 제 친구가 pypy를 쓰는데 시간초과가 났다고 함... )

Need Know

1. 재귀함수
2. 필요에 의하면 동적프로그래밍 (DP)

전체 코드 ( Java )

import java.io.*;
import java.util.StringTokenizer;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int N;
    static boolean[][] map;
    static int ans = 0;
    public static void main(String[] args) throws IOException {
        set();
        solve();

        bw.flush();
        bw.close();
        br.close();
    }

    static void set() throws IOException{
        N = Integer.parseInt(br.readLine());
        map = new boolean[N][N];

        StringTokenizer st;
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int k=0; k<N; k++){
                map[i][k] = !st.nextToken().equals("0");
            }
        }
    }
    static void solve() throws IOException {
        recursive_move(new Location(0,1,0));
        bw.write(ans + "");
    }
    static void printMap(){
        for(int i=0; i<N; i++){
            for(int k=0; k<N; k++){
                System.out.print(map[i][k] ? "1 " : "0 ");
            }
            System.out.println();
        }
    }

    /**
     * to nowLoc.direction
     * 0 : 가로
     * 1 : 대각선
     * 2 : 세로
     */
    static void recursive_move(Location nowLoc){
        if(nowLoc.x == N-1 && nowLoc.y == N-1){
            ans++;
            return;
        }

        if(nowLoc.direction == 0){
            if(nowLoc.y + 1 < N ){
                if(!map[nowLoc.x][nowLoc.y+1]){
                    if(nowLoc.x + 1 < N ) {
                        if (!map[nowLoc.x + 1][nowLoc.y] && !map[nowLoc.x + 1][nowLoc.y + 1]) {
                            map[nowLoc.x + 1][nowLoc.y + 1] = true;
                            recursive_move(new Location(nowLoc.x + 1, nowLoc.y + 1, 1));
                            map[nowLoc.x + 1][nowLoc.y + 1] = false;
                        }
                    }
                    map[nowLoc.x][nowLoc.y+1] = true;
                    recursive_move(new Location(nowLoc.x,nowLoc.y+1,0));
                    map[nowLoc.x][nowLoc.y+1] = false;
                }
            }
        }else if(nowLoc.direction == 1){
            if(nowLoc.y + 1 < N){
                if(!map[nowLoc.x][nowLoc.y+1]){
                    map[nowLoc.x][nowLoc.y+1] = true;
                    recursive_move(new Location(nowLoc.x,nowLoc.y+1,0));
                    map[nowLoc.x][nowLoc.y+1] = false;
                }
            }
            if(nowLoc.x + 1 < N){
                if(!map[nowLoc.x+1][nowLoc.y]){
                    map[nowLoc.x+1][nowLoc.y] = true;
                    recursive_move(new Location(nowLoc.x+1,nowLoc.y,2));
                    map[nowLoc.x+1][nowLoc.y] = false;
                }
            }
            if(nowLoc.x + 1 < N && nowLoc.y + 1 < N){
                if(!map[nowLoc.x+1][nowLoc.y+1] && !map[nowLoc.x+1][nowLoc.y] && !map[nowLoc.x][nowLoc.y+1]){
                    map[nowLoc.x+1][nowLoc.y+1] = true;
                    recursive_move(new Location(nowLoc.x+1,nowLoc.y+1,1));
                    map[nowLoc.x+1][nowLoc.y+1] = false;
                }
            }
        }else{
            if(nowLoc.x + 1 < N){
                if(!map[nowLoc.x+1][nowLoc.y]){
                    if(nowLoc.y + 1 < N){
                        if(!map[nowLoc.x][nowLoc.y+1] && !map[nowLoc.x+1][nowLoc.y+1]){
                            map[nowLoc.x+1][nowLoc.y+1] = true;
                            recursive_move(new Location(nowLoc.x+1,nowLoc.y+1,1));
                            map[nowLoc.x+1][nowLoc.y+1] = false;
                        }
                    }

                    map[nowLoc.x+1][nowLoc.y] = true;
                    recursive_move(new Location(nowLoc.x+1,nowLoc.y,2));
                    map[nowLoc.x+1][nowLoc.y] = false;
                }
            }
        }
    }
}
class Location{
    int x,y,direction;

    public Location(int x, int y, int direction) {
        this.x = x;
        this.y = y;
        this.direction = direction;
    }
}