[JavaScript] 백준 14500 테트로미노 (JS)

테트로미노

📚 문제 설명

N * M 크기의 지도의 각각에 칸에 숫자가 쓰여있다.
이 지도 위에 테트로미노 조각을 놓으려고 한다. 테트로미노가 놓여진 위치에 있는 숫자의 합이 최대가 되도록 했을 때의 값을 구하여라.

👨🏻‍💻 풀이 과정

길찾기 문제에서 자주 이용하는 DFS 함수를 진행하며 4칸을 이동한 후에 확인을 하면 그 모양은 반드시 테트로미노 모양 중 하나가 될 수 밖에 없다.
그러나 ㅜ 모양의 테트로미노의 경우 visited 함수를 이용해 지나온 길은 가지 않게 만드는 DFS 함수의 특성상 만들 수가 없다.

따라서 ㅜ 모양의 테트로미노를 위해 DFS 함수에 한가지 로직을 추가했다.

• 2칸을 이동했을 경우.
  • visited 배열의 다음 위치 체크.
  • DFS(현재위치, 이동거리 + 1, 숫자 계산값) 으로 재귀 진행.

이렇게 로직을 추가하면 ㄱ 자 모양까지 왔을 경우와 ㅣ 모양으로 3칸 갔을 경우 마지막으로 이동한 칸에서 한칸 나가는게 아니라 이전에 있던 칸에서 다음 칸으로 나아가게 되기 떄문에 ㅜ 모양의 테트로미노 모양을 만들 수 있게 된다.

전체 코드

    let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
    const [N, M] = input.shift().split(' ').map(Number);
    const MAP = input.map(v => v.split(' ').map(Number));
    let visited = Array.from({length: N}, _ => Array.from({length: M}, _ => false));
	// 최댓값 저장 변수.
    let max = 0;
	// DFS 함수.
    const DFS = (now, cnt, value) => {
      	// 4칸 이동시 종료.
        if (cnt === 4) {
            max = Math.max(max, value);
            return;
        }

        const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
      	
        for (const dir of dirs) {
            const NextX = now[0] + dir[0];
            const NextY = now[1] + dir[1];
          	// 맵 밖으로 나갈 경우 제외
            if (NextX < 0 || NextX >= N || NextY < 0 || NextY >= M) continue;

            if (!visited[NextX][NextY]) {
              	// 2칸 이동후 다음 이동.
                if (cnt === 2) {
                    visited[NextX][NextY] = true;
                    DFS(now, cnt + 1, value + MAP[NextX][NextY]);
                    visited[NextX][NextY] = false;
                }
              	// 일반적인 경우와 동일.
                visited[NextX][NextY] = true;
                DFS([NextX, NextY], cnt + 1, value + MAP[NextX][NextY]);
                visited[NextX][NextY] = false;

            }
        }
    };

    const solution = () => {
      	// N * M  모든 경우를 돌며 확인.
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < M; j++) {
              	// 시작 위치 체크.
                visited[i][j] = true;
                DFS([i, j], 1, MAP[i][j]);
              	// 다음 반복문을 위한 체크 해제.
                visited[i][j] = false;
            }
        }
    };
    solution();
    console.log(max);

🧐 후기

기본적으로 DFS 변형 문제라고 바로 생각이 들어서 접근 자체는 쉬웠으나 ㅜ 모양의 테트로미노 계산 때문에 고민했던 문제였다.