[백준] 17070. 파이프 옮기기 1

문제 링크

[백준] 17070. 파이프 옮기기 1

풀이 과정

DFS 문제입니다. 현재 파이프 모양과 다음 파이프 모양을 구분 짓고, 불가능한 경우들을 체크하여 문제를 풀었습니다.

static final int HORIZONTAL = 0, DIAGONAL = 1, VERTICAL = 2;
static int[] dx = {0, 1, 1}, dy = {1, 1, 0};

가로, 대각선, 세로를 각각 상수를 활용해 표현했고, 다음 좌표를 구하기 위한 델타 배열을 선언했습니다.

dfs(0, 1, HORIZONTAL);

좌표 (0, 1)에서 가로 방향을 주며 DFS 탐색을 시작합니다.

static void dfs(int x, int y, int dir) {
    if (x == N - 1 && y == N - 1) {
        answer++;
        return;
    }

    for (int d = 0; d < 3; d++) {
        if (dir == HORIZONTAL && d == VERTICAL) continue;
        if (dir == VERTICAL && d == HORIZONTAL) continue;

        int nx = x + dx[d], ny = y + dy[d];

        if (!inRange(nx, ny) || map[nx][ny] == 1) continue;
        if (d == DIAGONAL && (map[nx - 1][ny] == 1 || map[nx][ny - 1] == 1)) continue;

        dfs(nx, ny, d);
    }
}

dfs 메소드 는 가능한 모든 경로를 통해 (N-1, N-1) 좌표까지 도달합니다. 다음과 같이 동작합니다.

• 좌표가 (N-1, N-1)이면 끝까지 이동시켰으므로 answer 를 증가시켜 줍니다.
• 현재 방향 dir 과 파이프의 다음 방향 d 를 확인합니다.
  • dir 가 가로면, 파이프의 다음 모양으로 세로는 안되므로 패스합니다. 마찬가지로, dir 가 세로면 파이프는 다음 모양으로 가로를 띌 수 없으므로 건너뜁니다.
  • 다음 좌표가 범위 밖이거나, 벽이면 이동 못시키므로 건너뜁니다.
  • 바뀔 다음 모양이 대각선이면, 문제에서 제시한 세 지점에 벽이 있으면 안됩니다. 이를 확인하고 벽이 존재한다면 패스합니다.
  • 위 조건들을 다 통과한다면, 파이프를 다음 모양 d로 둘 수 있으므로 DFS 탐색을 계속 합니다.

코드

import java.util.Scanner;

public class Main {
    static int N;
    static final int HORIZONTAL = 0, DIAGONAL = 1, VERTICAL = 2;
    static int[] dx = {0, 1, 1}, dy = {1, 1, 0};
    static int[][] map;
    static int answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                map[i][j] = sc.nextInt();

        dfs(0, 1, HORIZONTAL);
        System.out.println(answer);
    }

    static void dfs(int x, int y, int dir) {
        if (x == N - 1 && y == N - 1) {
            answer++;
            return;
        }

        for (int d = 0; d < 3; d++) {
            if (dir == HORIZONTAL && d == VERTICAL) continue;
            if (dir == VERTICAL && d == HORIZONTAL) continue;

            int nx = x + dx[d], ny = y + dy[d];

            if (!inRange(nx, ny) || map[nx][ny] == 1) continue;
            if (d == DIAGONAL && (map[nx - 1][ny] == 1 || map[nx][ny - 1] == 1)) continue;

            dfs(nx, ny, d);
        }
    }

    static boolean inRange(int x, int y) {
        if (x < 0 || x > N - 1 || y < 0 || y > N - 1) return false;
        return true;
    }
}