[boj 16929] Two Dots -js

// Two Dots

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

const sol = (input) =>{
    const [N,M] = input.shift().split(' ').map(Number);
    const visited = Array.from(Array(N),()=>new Array(M).fill(false));
    const map = [];
    const dx = [0,0,-1,1];
    const dy = [1,-1,0,0];
    let start;
    let flag = false;
    for(let i=0; i<input.length; i++){
        map.push(input[i].split(''));
    }

    const dfs = (x,y,cnt,type) =>{
        if(flag) return;

        for(let i=0; i<4; i++){
            const nx = x+dx[i];
            const ny = y+dy[i];
            if(cnt>=4 && start[0] === nx && start[1] === ny){
                flag = true;
                return;
            }

            if(nx<0||ny<0||nx>=M||ny>=N||type !== map[ny][nx] || visited[ny][nx] === true){
                continue;
            }
        
            visited[y][x] = true;
            dfs(nx,ny,cnt+1,type);
            visited[y][x] = false;

        }
    }
    Out:for(let y=0; y<N;y++){
        for(let x=0; x<M;x++){
            start = [x,y];
            const type = map[y][x];

            dfs(x,y,1,type);
            visited[y][x] = false;
            if(flag) break Out;
            
        }
    }

    flag ? console.log("Yes") : console.log("No");
}

sol(input);

먼저 사이클을 찾는 dfs를 학습하고 오는것이 좋다.

 

사이클을 찾는 dfs의 원리는 쉽게 말하자면 dfs로 그래프를 탐색하면서 중복된 좌표가 탐색될 경우가 사이클이 있는 그래프이다.

또, 사이클의 조건을 주의한다.

 

이 문제의 경우 4개의 좌표를 가져야하는 사이클이다. 그러므로 좌표를 세는 카운트가 4이상이 될 경우와 이동 좌표가 처음 좌표와 같을 경우를 찾으면 된다. 하지만 방문처리를하며 비교할때 처음 시작하는 좌표의 값을 방문처리 하기 때문에 비교가 안되어 원하는 대로 동작을 안할 수가 있다. 이 부분을 주의하면 된다.

 

 

아 그리고 문법의 사소한 실수를 하며 한참을 헤맸는데

var ttt = [1,2,3];
console.log(ttt === [1,2,3]) // ?

이 콘솔의 출력은 무엇일까.. 바보같은 실수를 했다.