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

파이프 옮기기 1_17070

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

17070번: 파이프 옮기기 1

문제 설명

집 그래프가 NxN으로 주어진다. 

파이프를 (0,0)(0,1) 좌표에서 시작하여 오른쪽 하단 끝으로 이동시키는 방법의 수를 구한다.

집 그래프는 0과 1로 이루어지는데 1인경우는 벽이라서 이동할 수 없다.

 

파이프를 이동시킬 때는 3가지 방향이 있다.

가로, 세로, 오른쪽 하단을 바라보는 대각선

 

현재 바라보고있는 방향에 따라 이동할 수 있는 방법이 나눠진다.

가로: 가로, 대각선으로 가능

세로: 세로, 대각선으로 가능

대각선: 전부 가능

 

가로나 세로의 경우에는 이동할 위치에 벽이 없으면 되지만

대각선의 경우에는 세칸을 사용하므로 이동할 세칸에 모두 벽이 없어야한다.

시작할때는 파이프가 가로방향으로 주어진다.

---

문제 풀이

생각 과정

파이프라는 조건이 있어서 두칸씩 좌표를 사용하는 것 같지만 파이프의 처음부분은 어떤 조건에도 걸리지 않기 때문에

파이프의 끝이 바라보는 좌표만 가지고 구현을 해주면 된다.

 

브루트포스-dfs로 구현을했다.

0,1에서 시작하여 각 단계마다 바라보고 있는 방향을 저장해줬고

이동조건에 맞게 그대로 구현을 했다.

 

마지막 (N-1,N-1) 좌표에 도달하면 카운트를 늘려준다.

구현

public class 파이프옮기기_17070 {
    static int N, answer;
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        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++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0, 1, 1);
        System.out.println(answer);
    }

    public static void dfs(int y, int x, int dir) {    // dir 1:가로 2: 세로 3: 대각선
        if (y == N - 1 && x == N - 1) {
            answer++;
        }

        int ny, nx;
        if (dir == 1) { // 현재 가로인 경우
            // 가로 이동
            move(y, x + 1, 1);
        } else if (dir == 2) {  // 현재 세로인 경우
            // 세로 이동
            move(y + 1, x, 2);
        } else {    // 현재 대각선인 경우
            // 가로 이동
            move(y, x + 1, 1);
            // 세로 이동
            move(y + 1, x, 2);
        }
        // 대각선 이동
        move(y + 1, x + 1, 3);
    }

    public static void move(int ny, int nx, int dir) {
        if (ny < N && nx < N && arr[ny][nx] != 1) {
            if (dir == 3) {	// 대각선의 경우 추가 조건(총3칸이 비어있어야함)
                if (arr[ny - 1][nx] == 1 || arr[ny][nx - 1] == 1) return;
            }
            dfs(ny, nx, dir);
        }
    }
}