[백준 17070] - 파이프 옮기기(JAVA)

 

[문제] 

출처 - https://www.acmicpc.net/problem/17070

 

17070번: 파이프 옮기기 1

---

 

[문제풀이] 

 

DFS 를 활용하면 해결 할 수 있습니다. (N, N) 으로 이동시키는 모든 방법의 개수를 구해야 합니다.

파이프는 놓여진 방향에 따라 이동할 수 있는 방법이 다릅니다.

 

 

가로 - > 가로 or 대각선

세로 - > 세로 or 대각선

대각선 - > 가로 or 세로 or 대각선

* 모든 곳에서 대각선을 갈 수 있어서 코드에서는 대각선으로 가는 경우를 합쳐서 처리했습니다.

 

 

놓여진 방향을 처리해야 하므로 가로, 세로, 대각선을 의미하는 상태 변수 하나를 만들어

0 = 가로 , 1 = 세로 , 2 = 대각선 이라고 지정할 것입니다.

 

 

가로, 세로, 대각선 일 때 갈 수 있는 방향을 재귀함수를 사용해서 N, N 에 도달하면 방법의 개수를 증가시키고 return 을 시켜주면 답을 구할 수 있습니다. 다만 주의해야 할 점이 벽이있는 경우인데 가로 와 세로는 진행하는 방향에 벽이 있는지 없는지 확인하면 되지만 대각선의 방향에는 가로, 세로, 대각선 방향 모두 벽이 없어야합니다.

 

 

 

문제에서 대각선으로 가야할때는 꼭 빈 칸이어야 한다고 명시되어있기 때문입니다. 다른 문제 처럼 대각선에 벽이 없다해서 갈 수 있는 것이 아닙니다. 그래서 이점 주의해서 코드를 작성하면 됩니다.

 

 

 

---

 

[소스코드] 

 

 

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

public class Main {

    static int n, cnt;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        cnt = 0;
        StringTokenizer st;
        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());
            }
        }
        dfs(0, 1, 0);

        System.out.println(cnt);
    }


    // State = 0가로 , 1세로, 2 대각선
    static void dfs(int x, int y, int state) {
        if (x == n - 1 && y == n - 1) {
            cnt++;
            return;
        }

        if(state == 0){
            if(y+1 < n && map[x][y+1] == 0){
                dfs(x, y + 1, 0);
            }
        }else if(state == 1){
            if(x+1 < n && map[x+1][y] == 0){
                dfs(x+1, y, 1);
            }
        }else if(state == 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);
            }
        }

        if (x + 1 < n && y + 1 < n && map[x][y + 1] == 0 && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0) {
            dfs(x + 1, y + 1, 2);
        }

    }

}