[백준] no17070: 파이프 옮기기1 - DP/DFS/BFS — 궁금하신 점이 있다면 댓글로 남겨주세요.(2023년~ 노션으로 이동)

728x90

문제

 * 조건
 * 1. 파이프는 무조건 두 칸을 차지한다
 * 2. 첫 파이프는 항상 (1,1)(1,2)에 걸쳐있다 (길이가 2칸인 파이프)
 * 3. 파이프의 이동은 다음의 이동만 가능하다.
 *    가로일 때, 가로 or 오른쪽아래대각선
 *    세로일 때, 세로 or 오른쪽아래대각선
 *    대각선일 때, 가로 or 세로 or 오른쪽아래대각선
 * 4. 목표하는 N,N까지 이동이 가능한 경우의 수를 구해야 한다.
 * 5. 단, 중간에 이동이 불가능한 1인 칸이 있다면, 해당 경로는 지나칠 수 없다.
 * 6. 만약 대각선 이등을 해야한다면, 총 네칸을 차지한다.
 *
 * Input
 * 1. 사이즈 N
 * 2. 맵 현황 (0은 이동가느한 빈칸, 1은 이동불가한 벽)

문제 링크 : https://www.acmicpc.net/problem/17070

원리

1. BFS - Dijkstra 사용

1. dq를 반복하며,
2. 이전 상태가 가로일 때, 가로 조건으로 돌아
3. 이전 상태가 세로일 때, 세로 조건으로 돌아
4. 이전 상태가 대각선일 때, 대각선 조건으로 돌아

2. DFS

나의 코드

1. BFS 사용

1) 목적
: 너비 우선 탐색을 통한 모든 경우의 수 체크 (사실상 브루트 포스)

2) 특징
: 각 객체의 상태관리를 이용하는 방식으로 코드를 구현했다. 따라서 Enum을 통해 상태관리를 하므로, 3가지 이상의 상태를 적용할 수 있다.
: Dijkstra방식으로 반복문을 이용한 탐색을 구현했다. 따라서 경우에 따라 탐색 방법을 더욱 다각화 시킬 수 있다.

3) 한계점
: 사실상 모든 경우의 수를 구하는 브루트포스에 가깝다
: 메모리가 많이 소요된다

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

public class no17070 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N;
    private static boolean[][] field;

    // 현재상태가 가로일 때
    private static int[] verWidth = {0, 1};
    private static int[] horWidth = {1, 1};

    // 현재 상태가 세로일 때
    private static int[] verLength = {1, 1};
    private static int[] horLength = {0, 1};

    // 현재 상태가 대각선일 때
    private static int[] verDiagonal = {0, 1, 1};
    private static int[] horDiagonal = {1, 0, 1};

    public static void main(String[] args) throws IOException {

        N = Integer.parseInt(br.readLine());
        field = new boolean[N+1][N+1];
        StringTokenizer st;

        for(int i = 1; i<= N; i++) {
           st = new StringTokenizer(br.readLine(), " ");
           for(int j=1 ; j<= N; j++) {
               if(st.nextToken().equals("1")) field[i][j] = true;
           }
        }

        field[1][1] = field[1][2] = true;

        int result = BFS();

        System.out.println(result);
    }

    private static int BFS() {
        Deque<Node> dq = new ArrayDeque<>();
        // 처음은 무조건 가로이므로, 가로 방향에서 가능한 이동방식으로 초기화
        if(field[1][3]) return 0;

        if(field[2][2]) dq.add(new Node(1, 3, 0));
        else {
            for (int i = 0; i < horWidth.length; i++) {
                dq.add(new Node(1 + verWidth[i], 2 + horWidth[i], i)); // 가로 0 대각선 1
            }
        }

        int count = 0;
        
        while (!dq.isEmpty()) {
            Node now = dq.poll();

            if(now.Y==N && now.X==N) count++;

            // 가로
            if(now.NodeType==0) {
                for(int i=0 ; i<verWidth.length ; i++) {
                    if(i==0) {  // 가로 이동
                        if(now.X+1<=N &&
                                !field[now.Y][now.X+1]) dq.add(new Node(now.Y + verWidth[i], now.X + horWidth[i], 0));
                    }
                    else { // 대각선 이동 - 조건 : 4칸이 true
                        if(now.Y+1<=N && now.X+1 <= N &&
                                !field[now.Y][now.X+1] && !field[now.Y+1][now.X] && !field[now.Y+1][now.X+1]) dq.add(new Node(now.Y + verWidth[i], now.X + horWidth[i], 1));
                    }
                }
            }
            // 대각선
            else if(now.NodeType==1) {
                for(int i=0 ; i<verDiagonal.length ; i++ ) {
                    if(i==0) { // 가로이동
                        if(now.X+1 <= N &&
                                !field[now.Y][now.X+1]) dq.add(new Node(now.Y + verDiagonal[i], now.X + horDiagonal[i], 0));
                    } else if (i==1) { // 세로이동
                        if(now.Y+1<=N &&
                                !field[now.Y+1][now.X]) dq.add(new Node(now.Y + verDiagonal[i], now.X + horDiagonal[i], 2));
                    } else { // 대각선 이동
                        if(now.Y+1<=N && now.X+1 <= N &&
                                !field[now.Y][now.X+1] && !field[now.Y+1][now.X] && !field[now.Y+1][now.X+1]) dq.add(new Node(now.Y + verDiagonal[i], now.X + horDiagonal[i], 1));
                    }
                }
            }
            // 세로
            else {
                for(int i=0 ; i<verLength.length ; i++) {
                    if(i==0) {  // 세로 이동
                        if(now.Y+1 <= N &&
                                !field[now.Y+1][now.X]) dq.add(new Node(now.Y + verLength[i], now.X + horLength[i], 2));
                    }
                    else { // 대각선 이동 - 조건 : 4칸이 true
                        if(now.Y+1<=N && now.X+1 <= N &&
                                !field[now.Y][now.X+1] && !field[now.Y+1][now.X] && !field[now.Y+1][now.X+1]) dq.add(new Node(now.Y + verLength[i], now.X + horLength[i], 1));
                    }
                }
            }
        }
        return count;
    }

    private static class Node {
        private int Y, X, NodeType;

        private enum NodeType {
            width, diagonal, length   // 0, 1, 2
        }

        public Node(int y, int x, int nodeType) {
            this.Y = y;
            this.X = x;
            this.NodeType = nodeType;
        }
    }
}

2. DP 사용

1. 목적
: 메모리 단축 및 3차원 배열을 이용한 코드 간소화

2. 방법
: 3차원 배열 DP에서 1차원*2차원=입력된 맵 사이즈
: 3차원 배열 DP에서 3차원은 각각 0=가로, 1=세로, 2=대각선으로 상태 저장
: 좌표를 이동하며 각 좌표에 가로/세로/대각선으로 도달 가능한 수를 합쳐가면서 메모리제이션
: 최종 좌표 N, N에 도달하는 가로/세로/대각선 방식의 경우의 수를 합치면 N*N에 도달할 수 있는 모든 경우의 수가 됨

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N;
    /**
     * field : 입력받은 맵 형태로서, true는 곧 벽이 있다는 표시다.
     */
    private static boolean[][] field;
    /**
     * DP
     * : 가로, 세로, 대각선이 가능 한 경우를 모두 등록하기위한 3차원 배열
     * : 1, 2차원은 맵을 나타내며, 3차원은 각각 0은 가로, 1은 세로, 2는 대각선인 상태를 저장하는 방식이다. 
     */
    private static int[][][] DP; 

    public static void main(String[] args) throws IOException {
        
        // 입력구간
        N = Integer.parseInt(br.readLine());
        field = new boolean[N][N];
        DP = new int[N][N][3];
        StringTokenizer st;
        for(int i=0 ; i<N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0 ; j<N; j++) {
                if(st.nextToken().equals("1")) field[i][j] = true;
            }
        }

        
        DP[0][1][0] = 1; // 초기화
        
        // N * N을 순회하며, 구할 수 있는 경우를 순차적으로 칸마다 저장
        // 최종적으로 마지막 칸에 도달한 가로/세로/대각선은 각각의 구할 수 있는 경우의 수 합임
        for(int i=0 ; i<N ; i++) {
            for(int j=2 ; j<N ; j++) {
                // 가로일 때
                if (j-1 >= 0 && !field[i][j]) DP[i][j][0] = DP[i][j-1][0] + DP[i][j-1][2];
                // 세로일 때
                if (i-1 >= 0 && !field[i][j]) DP[i][j][1] = DP[i-1][j][1] + DP[i-1][j][2];
                // 대각선 일때
                if (i-1 >= 0 && j-1 >= 0 && !field[i][j] && !field[i-1][j] && !field[i][j-1]) {
                    DP[i][j][2] = DP[i-1][j-1][0] + DP[i-1][j-1][1] + DP[i-1][j-1][2];
                };
            }
        }

        // 최종 목적지에 도달할 때, 가로/세로/대각선으로 도달한 경우의 수를 모두 합치면 정답
        int result = DP[N-1][N-1][0] + DP[N-1][N-1][1] + DP[N-1][N-1][2];

        System.out.println(result);
    }

레퍼런스

참고 링크 : https://codeung.tistory.com/248 - DP

참고 링크 : https://steady-coding.tistory.com/30 - DFS

728x90

저작자표시 비영리 변경금지 (새창열림)

'알고리즘 저장소 (일반방식과 나만의 풀이) > JAVA' 카테고리의 다른 글

[백준] no11779: 최소비용 구하기2 - 다익스트라 (0)	2023.08.08
[백준] no9935: 문자열폭발 - Stack (0)	2023.08.06
[백준] no14938:서강그라운드 - 다익스트라(Dijkstra) (0)	2023.07.22
[백준] no2448: 별 찍기11 - 재귀 (0)	2023.07.20
[백준] no10830:행렬 제곱 - 분할정복 (0)	2023.07.18

문제

원리

나의 코드

레퍼런스

'알고리즘 저장소 (일반방식과 나만의 풀이) > JAVA' 카테고리의 다른 글

티스토리툴바