<Algorithm> 159. 파이프 옮기기2(BJO)

1. 17069번 파이프 옮기기2(BJO)

   사용 알고리즘 : DFS, DP 메모제이션, 백트래킹

• 처음에는 BFS 방식으로 하려고 했는데 BFS 보다는 DFS가 더 나을 것 같았다. 근데 요새 BFS만 쓰다보니 DFS를 구성하는데 헷갈렸다.

• BFS는 보통 순서가 있는데 이문제는 계속 탐색하면서 백트래킹을 해야했다. 즉 자주쓰는 Order을 만들 수 없었다.

• 이문제를 풀면서 DFS로 전구간 탐색하는 것을 다시 상기 시켰다.. 또 잊어버리면 이코드를 참조 해야겠다.

문제에 대한 접근&생각

1. 파이프는 3가지 모양이 있고 각각 움직이면서 모양을 바꿀 수 있는 가지수가 정해져 있다 -> 탐색조건!
2. 대각선 파이프는 움직일때 해당 칸의 3칸이 비어있어야 한다 -> 종료조건!
3. 파이프의 길이는 2고 앞의 위치가 움직인뒤 뒤의 위치는 이전의 앞의 위치가 된다 -> Queue 꼬리? BFS?
4. 3번을 잘생각해보면 앞의 위치가 맨끝점에 닿을 경우 탐색 종료임으로 뒤의 위치는 중요하지 않음 -> 앞의 위치로만 DFS!
5. 모든 가지로 뻗어나가는 경로에 대해서 탐색해야 함 -> DFS 백트래킹!
6. DFS 탐색 -> 시간초과...
7. 이미 경로를 탐색했던 곳은 재탐색 하지않게해서 연산을 줄임 -> DP 메모제이션!
8. 예시(경로는 맞지 않음, 이런 형태)

가로 [ 0 , 1]   - 가로(3)  -  가로(3) -  가로 - 길없음

 ( 시작점)                               - 대각선(3) - 가로 - 길없음

              - 세로(2)    - 세로     - 발견

                             - 대각선  - 발견

              - 대각선(1) - 가로     - 길없음

            - 세로     - 길없음

            - 대각선  - 발견

                  - 대각선(1) - ~~~ - 발견

※모든 경로(4)는 시작점에 저장된다.

내 코드 

import java.util.Scanner;
 
public class Main {
    static int[][] map;
    static int[][] imp = {{1,0,1},
                          {0,1,1},
                          {1,1,1}};
    // 모양별로 할 수 있는 모양
    static int[] dx = {0,1,1};
    static int[] dy = {1,0,1};
    static boolean[][] visited;
    static long [][][] path;
    static int n;
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        n = sc.nextInt();
        visited = new boolean[n][n];
        path = new long[3][n][n];
        map = new int[n][n];
        /******************************
         * DFS를 이용하여 모든 경로에 대해서
         * 갈수 있는지 판단한다. 이때 n이 크기 
         * 때문에 DP 메모제이션을 이용하여
         * 이미 탐색한 부분에 대한 경로를 저장하여
         * 탐색 수를 줄여서 끝점까지 갈수 있는
         * 경우의 수를 구한다.
         *******************************/
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        solve();
        
        System.out.println(path[0][0][1]);
    }
    
    public static void solve() {
        visited[0][1] = true;
        dfs(0, 1, 0);
    }
    public static long dfs(int x ,int y, int dir) {
        
        if(path[dir][x][y] != 0) 
            return path[dir][x][y];
        
        if(x == n-1 && y == n-1) 
            return 1;
        
        for(int i = 0; i < 3; i++) {
            if(imp[dir][i] == 1) {
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(boundary(nx, ny)&&!visited[nx][ny]&&map[nx][ny]!=1) {
                    if(i==2&&(map[nx][ny-1]==1||map[nx-1][ny]==1)) continue;
                    visited[nx][ny] = true;
                    path[dir][x][y] += dfs(nx, ny, i);
                    // 경로 갯수 메모제이션
                    visited[nx][ny] = false;
                }
                
            }
        }
        return path[dir][x][y];
    }
    private static boolean boundary(int nx,int ny) {
        if(nx < 0 || ny < 0|| nx >= n || ny >= n ) 
            return false;
        return true;
    }
    
}
 

 

참고 & 출처