백준 17070번 (java)

백준 17070 파이프 옮기기 1 java

---

관찰

n이 굉장히 작고 완전탐색 bfs나 dfs로 충분히 돌아갈 것 같다!
(파이프의 움직임이 수상하다 dp문제 같은 느낌이..)

---

1번째 시도 (bfs 시간초과)

빠르게 bfs로 구현하였지만 89%에서 시간초과..

---

2번째 시도 (dfs 정답)

bfs가 시간이 아깝게 초과돼서 혹시 하는 마음에 dfs로 바꾸어서 제출해보았다

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

public class Main {
    static class Node{
        int r;
        int c;
        int type;
        // type 1 가로, 2 세로, 3 대각선
        public Node(int r, int c, int type) {
            this.r = r;
            this.c = c;
            this.type = type;
        }
    }
    static int n; // 크기
    static int[][] map; // 맵
    static int cnt; // 가능한 횟수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        map = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        cnt = 0;
        //bfs();
        dfs(1,2,1);
        System.out.println(cnt);

    }
    
    private static void dfs(int r,int c,int type){
        if (r == n && c == n) {
            cnt++;
            return;
        }
        // 현재 가로 상태
        if (type == 1) {
            // 가로 이동 가능?
            if (isPossible(r, c + 1)) {
                dfs(r,c+1,1 );
            }
            // 대각선 이동 가능?
            if (isPossible(r, c + 1) && isPossible(r+ 1, c) && isPossible(r + 1, c + 1)) {
                dfs(r+1,c+1,3);
            }
        }
        // 현재 세로 상태
        else if (type == 2) {
            // 세로 이동 가능?
            if (isPossible(r + 1, c)) {
                dfs(r+1,c,2);
            }
            // 대각선 이동 가능?
            if (isPossible(r, c + 1) && isPossible(r + 1, c) && isPossible(r + 1, c + 1)) {
                dfs(r+1,c+1,3);
            }
        }
        // 현재 대각선 상태
        else {
            // 가로 이동 가능?
            if (isPossible(r, c + 1)) {
                dfs(r,c+1,1 );
            }
            // 세로 이동 가능?
            if (isPossible(r + 1, c)) {
                dfs(r+1,c,2);
            }
            // 대각선 이동 가능?
            if (isPossible(r, c + 1) && isPossible(r + 1, c) && isPossible(r + 1, c + 1)) {
                dfs(r+1,c+1,3);
            }
        }
    }
    
    // 실패 코드.. (시간초과)
    private static void bfs() {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(1, 2, 1));
        while (!q.isEmpty()) {
            Node cur = q.poll();
            int r = cur.r;
            int c = cur.c;
            if (r == n && c == n) {
                cnt++;
                continue;
            }
            // 현재 가로 상태
            if (cur.type == 1) {
                // 가로 이동 가능?
                if (isPossible(r, c + 1)) {
                    q.add(new Node(r, c + 1, 1));
                }
                // 대각선 이동 가능?
                if (isPossible(r, c + 1) && isPossible(r+ 1, c) && isPossible(r + 1, c + 1)) {
                    q.add(new Node(r + 1, c + 1, 3));
                }
            }
            // 현재 세로 상태
            else if (cur.type == 2) {
                // 세로 이동 가능?
                if (isPossible(r + 1, c)) {
                    q.add(new Node(r + 1, c, 2));
                }
                // 대각선 이동 가능?
                if (isPossible(r, c + 1) && isPossible(r + 1, c) && isPossible(r + 1, c + 1)) {
                    q.add(new Node(r + 1, c + 1, 3));
                }
            }
            // 현재 대각선 상태
            else {
                // 가로 이동 가능?
                if (isPossible(r, c + 1)) {
                    q.add(new Node(r, c + 1, 1));
                }
                // 세로 이동 가능?
                if (isPossible(r + 1, c)) {
                    q.add(new Node(r + 1, c, 2));
                }
                // 대각선 이동 가능?
                if (isPossible(r, c + 1) && isPossible(r + 1, c) && isPossible(r + 1, c + 1)) {
                    q.add(new Node(r + 1, c + 1, 3));
                }
            }
        }
    }
    private static boolean isPossible(int r, int c) {
        if(r < 1 || c < 1 || r > n || c > n){
            return false;
        }
        if(map[r][c] == 1){
            return false;
        }
        return true;
    }
}

;; dfs로 바꾸니깐 해결은 됐는데 찜찜해서 다른 풀이를 찾아보았더니 역시 dp로 푸는 방법이 있었다 파이프가 움직이는 규칙이 수상했다

---

3번째 시도 (dp 정답)

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

public class Main {
    static int n; // 크기
    static int[][] map; // 맵
    static int cnt; // 가능한 횟수
    static int[][][] dp; // dp..
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        map = new int[n+1][n+1];
        dp = new int[n+1][n+1][4];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        } 
        // 1 가로 2 세로 3 대각선
        //dp 시작 조건
        dp[1][2][1] = 1;
        for(int i=1; i<=n; i++){
            for(int j=2; j<=n; j++){
                if(i==1 && j==2) continue;
                // 가로로 두는 경우 - 가로 + 대각선
                if(map[i][j] == 0){
                    dp[i][j][1] = dp[i][j-1][1] + dp[i][j-1][3];
                }
                // 세로로 두는 경우 - 세로 + 대각선
                if(map[i][j] == 0) {
                    dp[i][j][2] = dp[i-1][j][2] + dp[i-1][j][3];
                }
                // 대각선으로 두는 경우 - 가로 + 세로 + 대각선
                if(map[i][j-1] == 0 && map[i-1][j] == 0 && map[i][j] == 0) {
                    dp[i][j][3] = dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2] + dp[i - 1][j - 1][3];
                }
            }
        }
        
        System.out.println(dp[n][n][1]+dp[n][n][2]+dp[n][n][3]);

    }
}

---

풀이

그림을 잘 보면 노란색처럼 가로로 오기 위해서는 오른쪽 칸에서 가로나 대각선로 와야한다, 초록색처럼 세로로 오기 위해서는 위 칸에서 세로니 대각선으로 와야한다, 마지막으로 파란색 처럼 대각선으로 오기 위해서는 우상칸에서 가로, 세로, 대각선으로 와야한다
이 규칙을 활용해서 dp 테이블을 채워주면 된다 (벽도 생각해주면서!)

---

느낀점

dfs와 bfs의 시간 차이를 느낄 수 있는 문제 + dp 연습!