[25.03.15] 파이프 옮기기 1

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

 

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

class Main {
    static int N;
    static int[][] arr;
    static int count=0;
    static int[] head = new int[2];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        for(int i=0; i<N; i++){
            String[] s = br.readLine().split(" ");
            for(int j=0; j<N; j++){
                arr[i][j]=Integer.parseInt(s[j]);
            }
        }
        //head[0] = i
        //head[1] = j
        head[1] = 1;
        dfs(head,0);
        System.out.printf("%d",count);
        
    }

    // 0 가로 , 1 세로 , 2 대각선
    public static void dfs(int[] head,int position){
        if(head[0]==(N-1) && head[1]==(N-1)){
            count++;
            return;
        }
        if(position==0){
            if(inMatrix(head,position,0)){
                int[] nextHead = new int[] {head[0], head[1]+1} ;
                dfs(nextHead,0);
            }
            if(inMatrix(head,position,2)){
                int[] nextHead = new int[] {head[0]+1, head[1]+1} ;
                dfs(nextHead,2);
            }
        }
        else if(position==1){
            if(inMatrix(head,position,1)){
                int[] nextHead = new int[] {head[0]+1, head[1]} ;
                dfs(nextHead,1);
            }
            if(inMatrix(head,position,2)){
                int[] nextHead = new int[] {head[0]+1, head[1]+1} ;
                dfs(nextHead,2);
            }
        }

        else{
            if(inMatrix(head,position,0)){
                int[] nextHead = new int[] {head[0], head[1]+1} ;
                dfs(nextHead,0);
            }
            if(inMatrix(head,position,1)){
                int[] nextHead = new int[] {head[0]+1, head[1]} ;
                dfs(nextHead,1);
            }
            if(inMatrix(head,position,2)){
                int[] nextHead = new int[] {head[0]+1, head[1]+1} ;
                dfs(nextHead,2);
            }
        }
    }

    public static boolean inMatrix(int[] head,int position, int nextPosition){
        if(position==0){
            if(nextPosition==0){
                if(canRight(head)){
                    return true;
                }
                return false;   
            }
                //대각선
            else{
                if(canDiagonal(head)){
                    return true;
                }
                return false;        
            }
        }
        else if(position==1){
            if(nextPosition==1){
                if(canDown(head)){
                    return true;
                }
                return false;   
            }
            else{ //대각선
                if(canDiagonal(head)){
                    return true;
                }
                return false;        
            }
        }
        else{
            if(nextPosition==0){
                if(canRight(head)){
                    return true;
                }
                return false;   
            }
            else if(nextPosition==1){
                if(canDown(head)){
                    return true;
                }
                return false;        
            }
            //대각선
            else{
                if(canDiagonal(head)){
                    return true;
                }
                return false;        
            }
        }
        
    }

    static boolean canRight(int[] head){
        if(head[1]+1<N && arr[head[0]][head[1]+1]==0){
            return true;
        }
        return false;
    }

    static boolean canDown(int[] head){
        if( head[0]+1<N && arr[head[0]+1][head[1]] == 0){
            return true;
        }
        return false;
    }

    static boolean canDiagonal(int[] head){
        if(head[0]+1<N && head[1]+1<N && arr[head[0]+1][head[1]]==0 && arr[head[0]][head[1]+1]==0 && arr[head[0]+1][head[1]+1]==0 ){
            return true;
        }
        return false;   
    }

}

 

진짜 너무 어거지로 풀었다.

DFS로 완탐쳤다. 

 

i,j 를 행,열의 인덱스로 본다면

현재 position이 오른쪽이라면 

1) 오른쪽 이동 (i,j+1)

2) 대각선 이동 (i+1,j+1)

 

현재 position이 아래쪽이라면

1) 아래쪽 이동 (i+1,j)

2) 대각선 이동 (i+1,j+1)

 

마지막으로 현재 position이 대각선이라면

1) 오른쪽 이동  (i,j+1)

2) 아래쪽 이동  (i+1,j)

3) 대각선 이동 (i+1,j+1)

 

의 케이스가 존재한다. 

 

이때 이동하기 전에 해당 이동방향에 대한 행,열 인덱스가 배열 안에서 유효한지 봐야한다. 이 유효의 기준은

1) 해당 행,열이 벽에 닿지 않는가? 

arr[이동 후 i] [이동 후 j] ==0

 

2) 해당 행, 열이 배열 안에 있는가?

0<= 이동 후 i < N , 0<= 이동 후 j < N

 

를 모두 판별해야한다.

 

또한 파이프라서 2개의 칸을 사용하고 있어 Head 부분 말고 뒷 칸의 파이프 부분도 파이프를 이동할때 벽에 닿는지 , 배열 안에서 유효한 좌표인지 확인해줘야 하지만, 현재 파이프는 무조건 오른쪽과 대각선, 즉 증가하는 방향으로 움직이기 때문에 파이프 뒷 부분에 대해서는 고려하지 않아도 항상 유효하다. (파이프의 Head 부분이 예외없이 항상 먼저 벽 또는 유효 배열 검사를 하기때문에) 

 

 저걸 모든 케이스에 대해 코드를 짠게 나의 방식이다. (솔직히 머릿속으로는 쉬웠지만 너무 쓸 코드가 많았다.)

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static int N;
    static int[][] map;
    static int ans;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        map = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        ans = 0;
        DFS(1, 2, 0);
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    // x는 세로, y는 가로
    // direction이 0일 때는 파이프가 가로 방향, 1일 때는 세로 방향, 2일 때는 대각선 방향.
    public static void DFS(int x, int y, int direction) {
        if (x == N && y == N) { // 종료 조건
            ans++;
            return;
        }
 
        switch (direction) {
        case 0: // 파이프가 가로 방향일 경우, 갈 수 있는 경우는 동쪽과 대각선임.
            if (y + 1 <= N && map[x][y + 1] == 0) { // 동쪽
                DFS(x, y + 1, 0);
            }
            break;
        case 1: // 파이프가 세로 방향일 경우, 갈 수 있는 경우는 남쪽과 대각선임.
            if (x + 1 <= N && map[x + 1][y] == 0) { // 남쪽
                DFS(x + 1, y, 1);
            }
            break;
        case 2: // 파이프가 대각선일 경우, 갈 수 있는 경우는 동쪽과 남쪽, 대각선임.
            if (y + 1 <= N && map[x][y + 1] == 0) { // 동쪽
                DFS(x, y + 1, 0);
            }
 
            if (x + 1 <= N && map[x + 1][y] == 0) { // 남쪽
                DFS(x + 1, y, 1);
            }
            break;
        }
 
        // 파이프가 어떤 방향이든지, 대각선은 검사해서 가장 아래로 뺐음.
        if (y + 1 <= N && x + 1 <= N && map[x][y + 1] == 0 && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0) {
            DFS(x + 1, y + 1, 2);
        }
    }
 
}