[JS] 백준 14500 : 테르로미노

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

 

📋풀이방법

1. 먼저 우리가 사용하는 DFS가 4까지 뻗어나간다고 했을 때 4가지의 테르미노는 회전과 대칭인 경우를 모두 탐색가능하다.

2.하지만 아래의 도형같은 경우는 DFS로 탐색이 안되므로 따로 탐색해야한다.

3. 위 도형같은 경우는 한 점을 중점으로 사방탐색을 하면된다.

사방 탐색을 하면서 3가지의 경우가 생기는데 아래와 같다.

 

📝코드 풀이 방식

1.모든 좌표를 순회한다 (i,j)

2. 좌표를 순회하면서 방문표시를해야한다(사방탐색시 왔던 곳은 다시 탐색할 수 없도록)

3. 좌표 하나씩 순회하면서 DFS(4가지 도형)와 otherFind(ㅓㅏㅜㅗ)를 수행한다

4. DFS

 -DFS는 좌표를 4개 탐색했을 때 종료한다(깊이가 4)

 -방문하지 않았던 곳을 사방탐색하면서 뻗어나간다.

 -이때 방문표시를 해주고 되돌아올때는 방문표시를 풀어준다.

 -DFS는 4가지 도형의 회전,대칭 모형까지 모두 탐색해주게 된다.

5. otherFind

 -ㅓㅏㅗㅜ 의 도형은 따로 탐색한다.

 - 중점좌표를 기준으로 사방탐색을 한다.

  -이때 탐색되는 횟수를 누적한다.

  -이때 탐색되는 좌표의 숫자를 더해 누적한다.

  -이때 탐색되는 좌표의 숫자 중 최솟값을 저장한다.

 -만약 사방탐색이 3번만 되었다면 ㅓㅏㅗㅜ가 성립 -> 그 값을 DFS가끝난 max값과 비교해 큰 값 저장

 -만약 사방탐색이 4번이 되었다면 +가 성립 -> 저장했던 최솟값을 빼서 성립되는 도형중 가장 큰 값을 저장

 -만약 사방탐색이 2번이하로 되었다면 도형이 성립안됨-> -1 리턴

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");


let [n,m]=input.shift().split(" ").map(Number);
let dx=[0,1,-1,0];
let dy=[1,0,0,-1];
let max=0;
let visited=Array.from({length:n},()=>Array(m).fill(false));

let arr=[];
for(var i of input){
    arr.push(i.split(" ").map(Number));
}
//// ㅡ ㄱ Z ㅁ 4가지의 모양을 탐색
function DFS(L,x,y,sum){
    if(L==4){
        max=Math.max(max,sum);
        return
    }
    for(var i=0;i<4;i++){
        let gx=x+dx[i];
        let gy=y+dy[i];
        // ㅡ ㄱ Z ㅁ 4가지의 모양을 탐색
        if(gx>=0 && gy>=0 && gx<m && gy<n && !visited[gy][gx]){
            visited[gy][gx] = true;//방문표시를 함으로써 사방탐색 할 때 갔던 곳은 못감
            DFS(L+1,gx,gy,sum+arr[gy][gx]);
            visited[gy][gx] = false;
        }
    }
    
}
//ㅓㅏㅗㅜ의 경우를 탐색
function otherFind(y,x){
    let base = arr[y][x];
    let cnt =0;
    let min = Number.MAX_VALUE;
    for(var i=0;i<4;i++){
        let nx=x+dx[i];
        let ny=y+dy[i];
        if(nx>=0 && ny>=0 && nx<m && ny<n){
            cnt++;
            base+=arr[ny][nx];
            min=Math.min(min,arr[ny][nx]);
        }
    }
    //4번탐색되면 그 중 최솟값을 빼서 ㅓㅏㅗㅜ도형 중 가장 큰 값을 가진 도형을 추출
    if(cnt==4){
        return base-min;
    }
    else if(cnt==3){
        return base;
    }
    else {
        return -1;
    }
}

for(var i=0;i<n;i++){
    for(var j=0;j<m;j++){
        visited[i][j] = true;
        DFS(1,j,i,arr[i][j]);
        max=Math.max(max,otherFind(i,j));
        visited[i][j] = false;
    }
}

console.log(max)

 

💢어려웠던 이유

1. DFS가 4가지 도형을 탐색할 수 있다는 것을 몰랐다.

 -하나의  좌표를 기준으로 DFS의 사방탐색을 깊이 4까지 뻗어나가면 4가지의 도형의 회전,대칭을 모두 탐색할 수 있다.

2. ㅓㅏㅗㅜ의  도형은 따로 계산해야한다는 것을 몰랐다.

 -ㅓㅏㅜㅗ는 DFS로 탐색이 불가능함 -> DFS가 되돌아올 때는 그 좌표를 빼버리니까

3.모든 좌표에서 하나의 좌표를 기준으로 두가지의 탐색방법을 수행해야한다는 생각을 못했다.

for(var i=0;i<n;i++){
    for(var j=0;j<m;j++){
        visited[i][j] = true;
        DFS(1,j,i,arr[i][j]);
        max=Math.max(max,otherFind(i,j));
        visited[i][j] = false;
    }
}

이 코드 방식으로 처음에 시작되어야하는 것을 파악하지 못했다.