백준 1941: 소문난 칠공주 - javascript(DFS/BFS)

문제 출처 

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

 

정답 풀이 

dfs로 상하좌우 이동하면서 조건에 맞는 (Y가 3이하) 학생으로 채우는 7명을 탐색한다면, 틀린다. 

왜냐하면 아래와 같이 T자 모양은 DFS로 만들지 못한다. 

 

 

따라서 , 2 부분으로 나눠서 구현해야 한다. 

1. DFS를 통한 7명의 학생 선택 

2. 선택된 7명의 학생이 인접한지 확인하는 BFS 

정답 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const graph = input.map(el => el.split(''));

function solution(graph) {
    let answer = 0;

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

    function isConnected(group) {
        // 선택된 7명의 좌표가 서로 인접해 있는지 BFS로 확인
        const queue = [group[0]];
        const visited = new Set([group[0].toString()]);
        let count = 1;

        while (queue.length) {
            const [x, y] = queue.shift();

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

                if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;

                for (let i = 0; i < group.length; i++) {
                    if (group[i][0] === nx && group[i][1] === ny && !visited.has([nx, ny].toString())) {
                        queue.push([nx, ny]);
                        visited.add([nx, ny].toString());
                        count++;
                    }
                }
            }
        }
        return count === 7; // 모두 연결되어 있는지 확인
    }

    function dfs(L, S, Y, group, start) {
        if (L === 7) {
            if (S >= 4 && isConnected(group)) {
                answer++;
            }
            return;
        }

        for (let idx = start; idx < 25; idx++) {
            const x = Math.floor(idx / 5);
            const y = idx % 5;

            if (graph[x][y] === 'S') {
                dfs(L + 1, S + 1, Y, [...group, [x, y]], idx + 1);
            } else if (graph[x][y] === 'Y' && Y + 1 < 4) {
                dfs(L + 1, S, Y + 1, [...group, [x, y]], idx + 1);
            }
        }
    }

    dfs(0, 0, 0, [], 0);

    return answer;
}

console.log(solution(graph));

틀린 코드 

//7명의 학생 
//가로 세로 인접 
//Y와 S가 함께 가능 , 그런데 S파가 우세해야함 4명 이상 

//전체 이중 반복문으로 입장 
//상하 좌우 이동 
//그때 Y가 4이상 되면 back 
//L ===7 일 때 그때 answer++; 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const graph = input.map(el => el.split(''))

function solution(graph){
    let answer = 0; 
    
    const dx = [-1,1,0,0];
    const dy = [0,0,-1,1];
    
    for(let i=0; i<5; i++){
        for(let j=0; j<5; j++){
             const visited= Array.from({length: 5}).map(() => new Array(5).fill(false))
             if(graph[i][j] === 'Y'){
                 visited[i][j] = true; 
                 dfs(0,0,1,i,j, visited)
                 visited[i][j] = false; 
             }
             else{
                 visited[i][j] = true; 
                 dfs(0,1,0,i,j, visited)
                 visited[i][j] = false; 
             }
             }
    }
    
    return answer; 
    
    function dfs(L,S,Y,x,y, visited){
        if(L === 7){
            answer++
            return; 
        }else{
            for(let d=0; d<4; d++){
                let nx = x + dx[d]
                let ny = y + dy[d]
                
                let name = graph[nx][ny]
                if(nx < 0|| ny <0 || nx >=5 || ny >= 5) continue; 
                if(visited[nx][ny]) continue; 
                if(name === 'Y' && Y + 1 >=4) continue 
                if(name === 'S'){
                    visited[nx][ny] = true; 
                    dfs(L+1, S+1, Y, nx, ny, visited)
                    visited[nx][ny] = false; 
                } else{
                    visited[nx][ny] = true; 
                    dfs(L+1, S, Y+1, nx, ny, visited) 
                     visited[nx][ny] = false; 
                }
               
            }
        }
    } 
}

console.log(solution(graph))