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

문제 설명

파이프를 옮겨 (n, n) 칸 까지 갈 수 있는 경우의 수가 총 몇 가지인지를 묻는 문제이다. 이때, 초반의 파이프는 무조건 (1, 1)과 (1, 2)를 차지하고 있고 총 세 가지 방향으로 움직일 수 있다.

 

파이프가 움직일 수 있는 방향은 오른쪽, 아래, 오른쪽 대각선 아래인데 이때 파이프는 45도 방향으로만 회전시킬 수 있다. 그렇기에 오른쪽 방향 파이프는 오른쪽 혹은 오른쪽 대각선 아래로만, 아랫 방향 파이프는 아래 혹은 오른쪽 대각선 아래로만, 오른쪽 대각선 아래 방향 파이프는 전부다 가능하다.

 

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

17070번: 파이프 옮기기 1

문제 풀이

일단 이렇게 탐색에서 모든 경우의 수를 찾는 문제는 높은 확률로 깊이 우선 탐색을 이용해야 한다. 왜냐하면 파이프의 끝에서 갈 수 있는 경우의 수가 적어도 2개 이상이기에, 주어진 조건을 맞추면서 끝까지 같다가 돌아와 다른 방향으로 탐색할 필요가 있기 때문이다.

 

1. 초기 설정

일단, n과 map으로 입력을 받은 다음 answer을 이용해서 모든 경우의 수를 세주기로 한다. 그리고 방향의 경우 나는 3차원 배열을 이용하였다.

public static int[][][] d = {{{0}, {1}}, {{1}, {0}}, {{1, 0, 1}, {1, 1, 0}}};

3차원 배열이라고 해서 복작하게 생각할 수 있는데, 단순히 풀어보자면 d[0][0][0]은 오른쪽 방향의 열의 첫 번째 방향이라고 할 수 있다. d[2][0][0] 같은 경우는 오른쪽 대각선 아랫 방향의 열의 대각선 아래 방향이라고 할 수 있고. 참고로 오른쪽 대각선 아랫 방향의 대각선 아랫 쪽을 첫 번째로 둔 것은 해당 방향이 파이프의 끝이기 때문이다.

 

사실 이렇게 방향 정하는 부분은 gold 5의 탐색 문제를 많이 풀어보면 쉽게 파악이 될 것이다.

 

2. (1, 1), (1, 2)에는 미리 방문하기

초기 (1, 1)과 (1, 2)에는 무조건 파이프가 있다고 했다. 그러므로 미리 탐색했다고 visit에 표시한 다음 파이프가 끝나는 부분인 (1, 2)에서부터 넓이 우선 탐색을 시작한다. 나는 0을 map에 포함하였으므로 (0, 1)에서부터 탐색을 했다.

 

3. 깊이 우선 탐색

재귀를 풀 때는 if - else 문을 이용하는 것이 편할 것이다. 일단 if 문에서는 r과 c가 끝까지 갈 때 answer에 1을 더해주고 return을 해준다. 그리고 else 에서는 탐색을 진행한다.

 

우리에게 주어진 방향은 총 3가지 이기에 3 가지 방향으로 탐색을 하면 된다. 이때 만일 num이 0이라 오른쪽이면 아래로 가는 방향인 1에서는 continue로 탐색을 패스하고 마찬가지로 num이 1이라 i가 0일 때는 탐색을 패스한다. 왜냐하면 우리는 파이프를 45도 각도로만 움직일 수 있기 때문이다.

 

그리고 탐색을 진행해준다. 우리는 배열을 [방향][행 or 열][해당 위치]로 지정해줬으므로 해당 방향으로 파이프가 갈 때 방문하는 총 칸의 갯수만큼 탐색을 해줘야 한다. 만일 이렇게 만든 새 위치가 배열 안에 들어가 있지 않으면 flag를 false로 돌리고 break를 한다. 배열에 들어가더라도 visit가 true라서 미리 방문을 했다거나 map이 1이라서 벽이라면 마찬가지로 flag를 false로 돌린 다음 break를 한다.

 

이렇게 파이프가 차지하는 위치가 모두 유효하여 flag가 true라면 비로서 해당 위치를 다시 한 번 확인하며 방문 표시 해준다. 그리고 재귀를 이용해 파이프의 끝 부분을 시작 부분으로 돌려 탐색한다. 참고로 오른쪽 대각선 아래 부분의 첫 번째 방향을 파이프의 끝으로 맞춰줬기 때문에 [해당 방향][열 or 행][0]의 값을 현재 좌표에 더한 값으로 재귀를 탐색한다. 만일 재귀가 끝나 해당 메소드가 종료됐다면 위에서 방문한 부분을 false로 돌려서 다시금 주변 위치를 탐색해주도록 한다.

코드

java

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


public class Main {
    public static int n;
    public static int[][] map;
    public static boolean[][] visit;
    public static int answer;

    public static int[][][] d = {{{0}, {1}}, {{1}, {0}}, {{1, 0, 1}, {1, 1, 0}}};

    public static void dfs(int r, int c, int num) {
        if (r == n-1 && c == n-1) {
            answer++;
            return;
        } else {
            for (int i=0; i<3; i++) {
                boolean flag = true;
                if (num == 0 && i == 1) {
                    continue;
                }
                if (num == 1 && i == 0) {
                    continue;
                }
                for (int j=0; j<d[i][0].length; j++) {
                    int nR = r + d[i][0][j];
                    int nC = c + d[i][1][j];
                    if (nR >= 0 && nR < n && nC >= 0 && nC < n) {
                        if (visit[nR][nC] || map[nR][nC] == 1) {
                            flag = false;
                            break;
                        }
                    } else {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    for (int j=0; j<d[i][0].length; j++) {
                        int nR = r + d[i][0][j];
                        int nC = c + d[i][1][j];
                        if (nR >= 0 && nR < n && nC >= 0 && nC < n) {
                            visit[nR][nC] = true;
                        }
                    }
                    dfs(r+d[i][0][0], c+d[i][1][0], i);
                    for (int j=0; j<d[i][0].length; j++) {
                        int nR = r + d[i][0][j];
                        int nC = c + d[i][1][j];
                        if (nR >= 0 && nR < n && nC >= 0 && nC < n) {
                            visit[nR][nC] = false;
                        }
                    }
                }
            }
        }
    }

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

    }

}