백준 16724 : 피리 부는 사나이 - javascript(dfs)

문제 출처 

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

 

정답 풀이 

아래 그림과 같이 화살표를 무작위로 그려봤을 때, 

dfs로 탐색을 해서 해당 연결이 끝나는 곳에 safe zone을 두면 되겠다는 아이디어가 떠오른다. 

그런데, 

visited 방문 처리로만 safe zone 을 다루면 안된다. 

 

왜냐하면 파란색 애들은 이미 방문 처리로 끝나고, 주황색 애들이 남아버린다. 

원래 같은 한 묶음이 될 수 있는데 !

 

어떻게 위와 같은 경우에도 한 묶음으로 만들 수 있을까? 

 

- dfs 반복문을 통해 사이클을 다 돈다.

=> visited[x][y] = 2 로 처리해둔다. 

- 또 아직 방문하지 않은 곳 dfs 반복문으로 돈다. 

=> 현재 돌고 있는 곳은 1로 처리, 

=> 1로 처리하다가 만약 자기 자신이 cycle에 있는 좌표를 만난다면,

=> 새로운 safeZone +1 이다. 

- 만약 2를 만난다면 

=> 기존 safeZone 에 편입되는 것이니, dfs 탐색을 그대로 중단한다.  

 

 

정답 코드 

 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [n, m] = input.shift().split(' ').map(Number);
const graph = input.map(line => line.split(''));
const visited = Array.from({ length: n }, () => new Array(m).fill(0)); // 0: 미방문, 1: 방문 중, 2: 방문 완료

let safeZone = 0;

for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
        if (visited[i][j] === 0) {
            dfs(i, j);
        }
    }
}

function dfs(x, y) {
    const cycle = [];
    
    while (true) {
        visited[x][y] = 1;
        cycle.push([x, y]);

        const [dx, dy] = dir(graph[x][y]);  
        x += dx;
        y += dy;

        if (x < 0 || y < 0 || x >= n || y >= m) return;

        if(visited[x][y] === 1){
            for(let [r,c] of cycle){
                if(x === r && y ===c){
                    safeZone+=1; 
                    break; 
                }
            }
            return; 
        }else if(visited[x][y] === 2){
            return; 
        }
    }

    // 탐색 완료된 곳을 2로 표시
    for (let [r, c] of cycle) {
        visited[r][c] = 2;
    }
}

function dir(direction) {
    switch (direction) {
        case 'U': return [-1, 0];
        case 'D': return [1, 0];
        case 'L': return [0, -1];
        case 'R': return [0, 1];
    }
}

console.log(safeZone);

 

정답 코드 2

//방향대로 움직여 
//상하좌우 
//최소개수 safe zone 

//dfs 알고리즘을 활용하자. 
//덩어리가 몇개인지 확인 
//-그런데, 덩어리가 편입 or 새로운 덩어리 

//방문하지 않은 곳이면 dfs 방문 
//거기서 dfs 탐색 
//해당 좌표 1로 
//만약 0이면 하나의 덩어리로 
//만약 1이면 그것이 이미 지금 탐색 중인 곳이면, 이제 끝내면서 safe zone +1 
//만약 2이면 그냥 편입임. return 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [n,m] = input.shift().split(' ').map(v => +v); 
let graph = input.map(el => el.split('')); 
const visited = Array.from({length: n}, () => new Array(m).fill(0)); 

let safeZone = 0; 

for(let i=0; i<n; i++){
    for(let j=0; j<m; j++){
        if(visited[i][j] === 0){
            dfs(i,j)
        }
    }
}

function dfs(x,y){
    let dung = [] ; 
    
    while(true){
     visited[x][y] = 1
     dung.push([x,y])
        
     let str = graph[x][y]
     let [dx,dy] = dir(str); 
     let nx = x+dx 
     let ny = y+dy 
     
     if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
            break;
        }
     if(visited[nx][ny] === 1){
            for(let [r,c] of dung){
                if(nx === r && ny === c){
                    safeZone+=1
                    break; 
                }
            }
            break; 
        }
        
      if(visited[nx][ny] === 2){
            return; 
        }
        
       x = nx 
       y = ny 
      }
    
 for(let [r,c] of dung){
      visited[r][c] = 2; 
    }       
}

function dir(str){
    switch(str){
        case 'U': 
            return [-1,0]
        case 'D': 
            return [1,0]
        case 'L': 
            return [0,-1]
        case 'R': 
            return [0,1]
        default: return [0,0]    
    }
}

console.log(safeZone)