[백준 17070] 파이프 옮기기1 (java)

문제풀이

 

카카오에 블록이동과 비슷한것 같지만 다른 문제입니다. 그때는 기준을 왼쪽 위(목적지와 상대적으로 가까운 지점)를 기준으로 잡았지만 이번에는 목적지와 상대적으로 가까운 지점을 기준으로 잡습니다.

 

그리고 현재 방향, 다음 방향을 모두 고려하여 불가능한 케이스를 제거해주고, 다음 위치의 벽유무, 범위 체크등을 해주며 dfs를 진행해 주면 되는 문제입니다.

소스코드

import java.util.Scanner;
 
public class Baekjoon17070 {
    static int mapSize;
    static final int VERTICAL=0;
    static final int HORIZONTAL=1;
    static final int DIAGONAL=2;
    static int[][] map;
    static int cnt =0;
 
    public static boolean isPossible(int row,int col, int dir, int nextDir){
        if(row>mapSize || col>mapSize)
            return false;
        if(nextDir==DIAGONAL){
            if(row+1>mapSize || col +1>mapSize)
                return false;
            if(map[row+1][col]==0 && map[row][col+1]==0 && map[row+1][col+1]==0)
                return true;
            return false;
        }else if(nextDir==VERTICAL){
            if(col+1>mapSize)
                return false;
            if(map[row][col+1]==0)
                return true;
            return false;
        }else{//HORIZONTAL
            if(row+1>mapSize)
                return false;
            if(map[row+1][col]==0)
                return true;
            return false;
        }
    }
    public static void dfs(int row,int col,int dir){
        if(row ==mapSize && col == mapSize){
            cnt++;
            return;
        }
 
        for(int i=0;i<3;i++){
            if(dir==VERTICAL && i==HORIZONTAL)
                continue;
            if(dir==HORIZONTAL && i==VERTICAL)
                continue;
            if(isPossible(row,col,dir,i)){
                if(i==DIAGONAL)
                    dfs(row+1,col+1,i);
                else if(i==VERTICAL)
                    dfs(row,col+1,i);
                else{
                    dfs(row+1,col,i);
                }
            }
 
        }
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        mapSize = scan.nextInt();
        map = new int[mapSize+1][mapSize+1];
 
        for(int i=1;i<=mapSize;i++){
            for(int j=1;j<=mapSize;j++){
                map[i][j] = scan.nextInt();
            }
        }
        dfs(1,2,VERTICAL);
        System.out.println(cnt);
    }
}
 

 

문제 링크 : www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1