[Baekjoon] 백준 17070번: 파이프 옮기기 1 (JAVA)

문제 17070

17070번: 파이프 옮기기 1

 

[ 풀이 과정 ]

(1, 1) 에서 (N, N) 까지 가는 경우의 수를 구하는 것이기 때문에 그래프 탐색 방법인 BFS, DFS가 떠올랐습니다.

흔히 그래프 탐색 문제는 현재 좌표에서 상하좌우 또는 대각선까지 갈 수 있는 좌표를 모두 탐색하는 것이 대부분이지만, 이 문제에서는 현재 좌표에서 갈 수 있는 방향이 오른쪽, 아래쪽, 대각선(오른쪽 아래) 이렇게 총 3가지이고, N의 범위도 3 ~ 16으로 작습니다. BFS로 풀게 될 경우, 같은 정점이 반복해서 Queue에 들어가게 되기 때문에 DFS로 풀었습니다.

방향이 3가지 밖에 되지 않기 때문에 풀이 과정은 비교적 간단합니다. 시작 좌표는 문제에서 주어진 것과 같이 무조건 (1, 1) 이므로 배열의 특성을 생각해 (0, 0) 부터 (N-1, N-1)로 풀었습니다.

현재 좌표에서 파이프의 방향도 함께 저장해주어야 하기 때문에 dfs() 의 매개변수로 좌표의 행, 열과 방향을 주었습니다. 파이프의 방향이 가로, 세로, 대각선일 때 각각 이동할 수 있는 파이프의 방향이 정해져 있으므로 switch 구문을 이용하여 재귀적으로 풀었습니다.

현재 위치에서 3방향으로 이동할 때 범위를 벗어나지 않는지, 빈 칸인지 체크하는 함수를 만들었습니다. 

[ 코드 ]

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

public class Main {
    private static int N, res;
    private static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        res = 0;

        map = new int[N][N];
        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());
            }
        }

        // 방향: 가로 -1, 대각선 0, 세로 1
        dfs(0, 1, -1);
        bw.write(String.valueOf(res));
        bw.flush();
    }

    private static void dfs(int r, int c, int direction) {
        if (r == N-1 && c == N-1) {
            res++;
            return;
        }

        switch (direction) {
            case -1:
                // 가로 or 대각선
                if (checkEast(r, c)) dfs(r, c+1, -1);
                if (checkDiagonal(r, c)) dfs(r+1, c+1, 0);
                break;
            case 0:
                // 가로 or 세로 or 대각선
                if (checkEast(r, c)) dfs(r, c+1, -1);
                if (checkSouth(r, c)) dfs(r+1, c, 1);
                if (checkDiagonal(r, c)) dfs(r+1, c+1, 0);
                break;
            case 1:
                // 세로 or 대각선
                if (checkSouth(r, c)) dfs(r+1, c, 1);
                if (checkDiagonal(r, c)) dfs(r+1, c+1, 0);
                break;
        }
    }

    private static boolean checkEast(int r, int c) {
        return c + 1 < N && map[r][c + 1] == 0;
    }

    private static boolean checkSouth(int r, int c) {
        return r+1 < N && map[r+1][c] == 0;
    }

    private static boolean checkDiagonal(int r, int c) {
        if (r+1 < N && c+1 < N) {
            return map[r + 1][c] == 0 && map[r + 1][c + 1] == 0 && map[r][c + 1] == 0;
        }
        return false;
    }
}