[Java] BOJ/백준 17070번 파이프 옮기기 1

[문제]

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

17070번: 파이프 옮기기 1

 

 

[풀이]

약간.. 구현문제에 DFS 살짝 추가한 정도의 문제 같다.

그냥 7가지 경우의 수에 따라 파이프의 한쪽 끝이 원하는 위치에 도달할 때까지 깊이 우선 탐색을 진행한다.

 

아래 5가지에 유의하면서 풀었다.

1. 파이프 끝점을 기준으로 한다.

2. 파이프 주위 꼭 빈칸이어야 하는 곳에 벽이 있을 경우 파이프를 이동할 수 없다.

3. 파이프가 가로일 경우, 가로로 한 칸 혹은 대각선으로 한 칸 이동한다.

4. 파이프가 세로일 경우, 세로로 한 칸 혹은 대각선으로 한 칸 이동한다.

5. 파이프가 대각선일 경우, 가로로 한 칸 혹은 세로로 한 칸 혹은 대각선으로 한 칸 이동한다.

 

파이프의 방향을 1, 2, 3으로 지정해 1일 때는 가로 방향, 2일 때는 세로 방향, 3일 때는 대각선 방향으로 구분했다.

또, 파이프가 가로, 세로, 대각선일 경우 모두 파이프를 대각선으로 이동시킬 수 있어 이는 switch문 밖으로 뺐다.

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N, answer = 0;
    static int[][] house;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        house = new int[N][N];
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                house[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0, 1, 1);
        System.out.println(answer);
    }

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

        switch (direction) {
            case 1:
                if (y + 1 < N && house[x][y + 1] == 0) dfs(x, y + 1, 1);
                break;
            case 2:
                if (x + 1 < N && house[x + 1][y] == 0) dfs(x + 1, y, 2);
                break;
            case 3:
                if (y + 1 < N && house[x][y + 1] == 0) dfs(x, y + 1, 1);
                if (x + 1 < N && house[x + 1][y] == 0) dfs(x + 1, y, 2);
                break;
            default: break;
        }
        if (x + 1 < N && y + 1 < N 
            && house[x][y + 1] != 1 && house[x + 1][y] != 1 && house[x + 1][y + 1] != 1) {
                dfs(x + 1, y + 1, 3);
        }
    }
}