17070

백준 17070번

Link: 17070번: 파이프 옮기기 1

---

문제 설명

오늘도 BFS 문제다.

전형적인 BFS와는 다른 방식으로 풀어야 하는 문제였다.

보통 BFS의 경우 1 * 1짜리 한칸만 고려해줘도 풀리는 문제들이 대다수인데 이 문제같은 경우 파이프의 앞, 뒤를 함께 고려해야 한다는 점이 큰 차이점이었다.

이외에도 회전하는 조건이 꽤 까다롭다는 점이 차이점이었으며 반복 방문을 막기 위해 BFS에서 보통 사용하는 visit 배열을 쓰지 않아야 풀리는 문제라는 점도 차이점이다.

그리고 이 문제의 경우 BFS로 풀면 88%에서 시간초과가 난다.

혹시나 해서 DFS로 바꿔서 풀어보니 바로 풀렸다.

DFS는 재귀호출이기 때문에 함수 호출에 걸리는 시간도 있으니 BFS보다 더 오래 걸릴것이라고 생각했는데 잘못 생각했던것 같다.

조건이 꽤 많은데 이 조건들을 하나하나 반영하며 DFS로 풀면 바로 풀리는 문제였다.

---

정답 코드

package Baekjoon;

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

public class Main_17070 {
    static class Pipe{
        int frontX, frontY;

        int direction;

        public Pipe(int frontX, int frontY, int direction) {
            this.frontX = frontX;
            this.frontY = frontY;
            this.direction = direction;
        }
    }

    static int[] dx = {0, 1, 1};
    static int[] dy = {1, 1, 0};
    static int[][] map;
    static int N;
    static int count;

    public static void DFS(Pipe start) {
        int currentFrontX = start.frontX;
        int currentFrontY = start.frontY;
        int currentDirection = start.direction;

        if(currentFrontX == N && currentFrontY == N) {
            count++;
            return;
        }

        for(int i=0; i<3; i++) {
            int nextFrontX = currentFrontX + dx[i];
            int nextFrontY = currentFrontY + dy[i];
            int nextDirection = i;

            if((currentDirection == 0 && nextDirection == 2) || (currentDirection == 2 && nextDirection == 0)) {
                continue;
            }

            if(i == 1) {
                if(nextFrontX <= N && nextFrontY <= N) {
                    if(map[nextFrontX][nextFrontY] == 0 && map[currentFrontX][currentFrontY] == 0 && map[nextFrontX][nextFrontY - 1] == 0 && map[currentFrontX][currentFrontY + 1] == 0) {
                        DFS(new Pipe(nextFrontX, nextFrontY, nextDirection));
                    }
                }
            }
            else {
                if(nextFrontX <= N && nextFrontY <= N) {
                    if(map[nextFrontX][nextFrontY] == 0 && map[currentFrontX][currentFrontY] == 0) {
                        DFS(new Pipe(nextFrontX, nextFrontY, nextDirection));
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        count = 0;

        map = new int[N+1][N+1];

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

        Pipe start = new Pipe(1, 2, 0);

        DFS(start);

        System.out.println(count);
    }

}

---