[JavaScript] 백준 17070 파이프 옮기기 1 (JS)

SanE·2024년 4월 22일

DFS JavaScript algorithm dynamic programming 백준

📚 문제 설명

N * N 크기의 판에 파이프가 (0,0), (0,1) 위치에 가로로 놓여 있다.
이 때 이 파이프를 옮겨서 파이프 한쪽 끝을 (N,N) 위치에 두는 경우의 수를 구하여라.

단, 파이프가 놓여있는 방향(가로,세로,대각선)에 따라 움직일 수 있는 방향이 달라진다.
자세한 내용은 문제 링크를 통해 확인하자.

👨🏻‍💻 풀이 과정

결국 파이프는 처음에 가로로 시작해서 최종적으로 한쪽 끝이 (N,N) 위치에 놓이면 된다.
따라서 가장 처음 생각했던 방법은 DFS를 이용하는 방식이었다.

💡DFS(깊이 우선 탐색)

파이프의 양쪽 끝을 인자로 받게 구현하여, 파이프의 모양에 따라 재귀를 진행한다.
( DFS풀이의 경우 머리속에서 생각나는 그대로 구현하여 코드가 조금 지저분하다.)

한쪽 끝이 (N,N)에 오면 종료.
파이프의 모양에 따라 다음 위치로 이동 후 재귀.

전체 풀이

    let fs = require("fs");
    let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = parseInt(input.shift());
    let map = input.map(v => v.split(' ').map(Number));
    let answer = 0;
	// 깊이 우선 탐색
    const DFS = (StartX, StartY, EndX, EndY) => {
      	// 종료 조건.
        if (EndX === N - 1 && EndY === N - 1) {
            answer++;
            return;
        }
      	// 가로 모양.
        if (StartX === EndX && StartY < EndY) {
          	// 가로로 한칸 이동. (가로 모양)
            if (EndY + 1 < N && map[EndX][EndY + 1] !== 1) {
                DFS(EndX, EndY, EndX, EndY + 1);
            }
          	// 대각선 우측 아래로 이동. (대각선 모양)
            if (EndY + 1 < N && EndX + 1 < N && map[EndX][EndY + 1] !== 1 && map[EndX + 1][EndY + 1] !== 1 && map[EndX + 1][EndY] !== 1) {
                DFS(EndX, EndY, EndX + 1, EndY + 1);
            }
        // 세로 모양.
        }else if (StartX < EndX && StartY === EndY) {
          	// 세로로 한칸 이동. (세로 모양)
            if (EndX + 1 < N && map[EndX + 1][EndY] !== 1) {
                DFS(EndX, EndY, EndX + 1, EndY);
            }
          	// 대각선 우측 아래로 이동. (대각선 모양)
            if (EndY + 1 < N && EndX + 1 < N && map[EndX][EndY + 1] !== 1 && map[EndX + 1][EndY + 1] !== 1 && map[EndX + 1][EndY] !== 1) {
                DFS(EndX, EndY, EndX + 1, EndY + 1);
            }
        // 대각선 모양.
        } else {
          	// 세로로 한칸 이동. (세로 모양)
            if (EndX + 1 < N && map[EndX + 1][EndY] !== 1) {
                DFS(EndX, EndY, EndX + 1, EndY);
            }
          	// 가로로 한칸 이동. (가로 모양)
            if (EndY + 1 < N && map[EndX][EndY + 1] !== 1) {
                DFS(EndX, EndY, EndX, EndY + 1);
            }
          	// 대각선 우측 아래로 이동. (대각선 모양)
            if (EndY + 1 < N && EndX + 1 < N && map[EndX][EndY + 1] !== 1 && map[EndX + 1][EndY + 1] !== 1 && map[EndX + 1][EndY] !== 1) {
                DFS(EndX, EndY, EndX + 1, EndY + 1);
            }
        }
    };

    DFS(0, 0, 0, 1);
    console.log(answer);

이렇게만 구현해도 무사히 통과할 수 있었으나 통과한 다른 사람들의 코드 길이와 시간을 보고 코드를 수정해야 한다고 느꼈다.

따라서 Dynamic Programming을 이용해 코드를 수정하게 되었다.

💡Dynamic Programming(DP)

dp[x][y][가로] 는 x, y위치의 가로로 놓인 파이프의 경우의 수라고 할 때
점화식으로 표현하면 다음과 같이 생각할 수 있다.

dp[x][y][가로] = dp[x][y - 1][가로] + dp[x - 1[y - 1][대각선]
dp[x][y][세로] = dp[x - 1][y][세로] + dp[x - 1[y - 1][대각선]
dp[x][y][대각선] = dp[x][y - 1][가로] + dp[x - 1][y][세로] + dp[x - 1[y - 1][대각선]

이를 바탕으로 코드를 작성하면 다음과 같다.

전체 풀이

    let fs = require("fs");
    let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = parseInt(input.shift());
    let map = input.map(v => v.split(' ').map(Number));
    // 각각의 위치의 [가로, 세로, 대각] 갯수로 저장.
    let Pipes = new Array(N).fill(0).map(v => new Array(N).fill(0).map(v => new Array(3).fill(0)));
	// 격자 맨위는 무조건 경우의 수 1개이다.
    for (let i =1; i < N; i++) {
      	// 벽이면 생략.
        if (map[0][i] === 1) break;
      	// 무조건 가로 파이프.
        Pipes[0][i][0] = 1;
    }
	// 메인 함수.
    const solution = () => {
      	// 2중 for문을 이용해 전체 위치 확인.
        for (let i = 1; i < N; i++) {
            for (let j = 1; j < N; j++) {
              	// 다음 위치가 벽이면 생략.
                if (map[i][j] === 1) continue;
              	// 가로
                Pipes[i][j][0] = Pipes[i][j - 1][0] + Pipes[i][j - 1][2];
              	// 세로
                Pipes[i][j][1] = Pipes[i - 1][j][1] + Pipes[i - 1][j][2];
              	// 대각선일 경우 벽을 확인할 영역이 추가됨.
                if (map[i][j - 1] === 1 || map[i - 1][j] === 1) continue;
              	// 대각선일 경우.
                Pipes[i][j][2] = Pipes[i - 1][j - 1][0] + Pipes[i - 1][j - 1][1] + Pipes[i - 1][j - 1][2];
            }
        }
    };
    solution();
	// N,N 위치의 모든 파이프를 더해서 확인.
    console.log(Pipes[N - 1][N - 1].reduce((acc, cur) => acc + cur, 0));