백준 14500: 테트로미노 - javascript (완탐, dfs)

문제 출처 

https://www.acmicpc.net/problem/14500

 

정답 풀이 

테트로미노 다섯가지 모양을 보면, dfs 탐색으로 커버 가능하다는 것을 알 수 있다. 

단, ㅗ 모양 빼고 ! 

 

- 따라서 dfs 를 통해 cnt가 4가 될 때까지 탐색하고, 

- 최대 합을 구한다. 

- 따로, 'ㅗ','ㅏ',ㅜ'','ㅓ' 모양일 때 전체 합을 구한다. 

정답 코드 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [n, m] = input.shift().split(' ').map(v => +v); 
const graph = input.map(el => el.split(' ').map(v => +v));

const dx = [-1, 1, 0, 0]; 
const dy = [0, 0, -1, 1]; 
let max = 0; 

const visited = Array.from({ length: n }, () => new Array(m).fill(false));

for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
        visited[i][j] = true; 
        dfs(i, j, graph[i][j], 1);
        visited[i][j] = false;
        check(i, j); 
    }
}

console.log(max);

function dfs(x, y, sum, cnt) {
    if (cnt === 4) {
        max = Math.max(max, sum);
        return; 
    }

    for (let d = 0; d < 4; d++) {
        const nx = x + dx[d]; 
        const ny = y + dy[d]; 

        if (nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny]) continue; 

        visited[nx][ny] = true;
        dfs(nx, ny, sum + graph[nx][ny], cnt + 1);   
        visited[nx][ny] = false;
    }
}

// 'ㅗ', 'ㅜ', 'ㅏ', 'ㅓ' 모양을 처리하기 위한 함수
function check(x, y) {
    const shape = [
        [[0,1],[-1,1],[0,2]],//ㅗ
        [[0,1],[1,1],[0,2]],//ㅜ
        [[1,0],[1,1],[2,0]],//ㅏ
        [[1,0],[1,-1],[2,0]],//ㅓ
    ]
    for(let el of shape){
       let sum = graph[x][y] 
       for(let [dx, dy] of el){
           const nx = x+dx
           const ny = y+dy
           if(nx < 0 || ny < 0 || nx >= n || ny >= m) break; 
           sum+= graph[nx][ny]
       }
        max = Math.max(max, sum)
    }
}