백준 - 17070 파이프 옮기기1(Java)

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

17070번: 파이프 옮기기 1

 

DFS 문제입니다.

기본 DFS 문제들은 한 칸씩만 고려해 문제를 풀 수 있었지만, 이 문제는 파이프가 두 칸을 차지하길래 어떻게 풀어야할지 고민을 많이 했습니다.

하지만, 여기에 함정이 있습니다.

파이프는 처음에 두 칸을 먹지만, 파이프 끝을 기준으로 한 칸씩만 움직이고 있습니다.

또한, 처음 시작 위치는 (1,1)로 고정입니다.

문제에 "가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다." 라고 나와 있기 때문에 (1, 2)부터 시작하고 한 칸씩 움직이며 조건에 따라 DFS 탐색을 다르게 해주면 됩니다.

 

처음에 이미 방문했던 곳을 다시 방문하지 않기 위해 visited라는 배열을 선언하여 사용했습니다.

하지만, 매 번 visited를 복사해서 DFS 탐색을 해야했기 때문에 시간 초과가 발생했습니다.

 

visited를 삭제한 결과 문제를 맞출 수 있었습니다.

 

※ 무조건 visited를 사용한다 해서 시간이 줄어들지 않는다. 오히려 더 늘어날 수 있다.

 

[구현 코드]

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

public class Main {
    private static int n, ans;

    /*
     * 0 : 가로
     * 1 : 세로
     * 2 : 대각선
     * */
    private static int[][] dx = {
            {0, 1},
            {1, 1},
            {0, 1, 1}
    };
    private static int[][] dy = {
            {1, 1},
            {0, 1},
            {1, 0, 1}
    };

    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 stz;


        n = Integer.parseInt(br.readLine());
        int[][] map = new int[n + 1][n + 1];
        for (int i = 1; i < n + 1; i++) {
            stz = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j < n + 1; j++) {
                map[i][j] = Integer.parseInt(stz.nextToken());
            }
        }

        ans = 0;
        dfs(map, 0, 1, 2, 0);

        bw.write(String.valueOf(ans));

        bw.flush();
        bw.close();
        br.close();
    }


    private static void dfs(int[][] map, int shape, int r, int c, int cnt) {
        if (r == n && c == n) {
            ans++;
            return;
        }

        for (int i = 0; i < dx[shape].length; i++) {
            int nx = r + dx[shape][i];
            int ny = c + dy[shape][i];

            if (nx < n + 1 && ny < n + 1) {

                // 대각선 빈칸 판단
                if (i == dx[shape].length - 1) {
                    if (!(nx - 1 >= 0 && ny - 1 >= 0)) continue;
                    if (map[nx - 1][ny] == 1 || map[nx][ny - 1] == 1) continue;
                }

                if (map[nx][ny] == 0) {
                    int ns;

                    // 현재 가로나 세로
                    if ((shape == 0 || shape == 1)) {
                        // 다음이 대각선이 아니라면 모양 유지
                        if (i == 0) {
                            ns = shape;
                        } else {
                            // 대각선
                            ns = 2;
                        }
                    } else {
                        // 현재 대각선이고 다음은 i값에 따라 달라짐
                        ns = i;
                    }

                    dfs(map, ns, nx, ny, cnt + 1);
                }

            }
        }
    }

}