[JavaScript/BFS/백트래킹] 백준 골드 3 : 1941 - 소문난 7공주

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

1941번: 소문난 칠공주

---

📌 작성한 코드 

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

const board = input.map((str) => str.split(""));

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

let arr = new Array(7);
let answer = 0;

const permutation = (at, count, sCount) => {
    if (count === 7) {
        if (sCount >= 4) bfs([...arr]);
        return;
    }

    for (let i = at; i < 25; i++) {
        arr[count] = i;
        const isSom = board[Math.floor(i / 5)][i % 5] === "S" ? 1 : 0;
        permutation(i + 1, count + 1, sCount + isSom);
    }
};

const bfs = (list) => {
    const queue = [];
    const visited = Array(7).fill(false);
    queue.push(list[0]);
    visited[0] = true;
    let count = 1;

    let idx = 0;
    while (queue.length > idx) {
        const node = queue[idx++];
        const x = Math.floor(node / 5);
        const y = node % 5;

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

            for (let j = 1; j < 7; j++) {
                const next = list[j];
                const nextX = Math.floor(next / 5);
                const nextY = next % 5;

                if (!visited[j] && nx == nextX && ny === nextY) {
                    visited[j] = true;
                    queue.push(list[j]);
                    count++;
                }
            }
        }
    }

    if (count === 7) {
        answer++;
    }
};

permutation(0, 0, 0);
console.log(answer);

📌 설명 

소문난 7공주 파를 결성할 수 있는 경우의 수를 구하는 문제이다. 문제를 처음 봤을 때는 bfs/dfs로 구할 수 있을 거라 생각했지만, 경로를 구하는 것이 아니라 분기점이 존재할 수 있기 때문에 단순하게 bfs를 한 번 돌려서는 구할 수 없는 문제이다. 

 

아래 사진에서 (2)번째 경우를 보면 왜 bfs로 불가능한 지 이해할 수 있다. (1,1) 위치에서 오른쪽과 아래쪽으로 분기점이 생기게 되는데, bfs를 사용하게 되면 각각의 루트에 대한 개수를 세기 때문에 전체 방문한 개수를 세서 7개가 될 때를 구하기가 어렵다. (아래로 내려가는 루트의 종점에서의 개수 4, 옆으로 가는 루트에서 종점의 개수 5 -> 전체 7개임을 계산하기 어려움) 

그래서 사용할 수 있는 방법은 가능한 7명의 조합을 모두 구한 뒤에, 7공주 파의 규칙에 해당하는 조합의 개수를 구하는 것이다.

 

(1) 이다솜파가 4명 이상인 7명 조합을 백트래킹으로 구하기

- 순서에 상관없이 7명을 선택할 것이므로, 오름차순으로 조합을 구하는 방식을 사용하였다. at을 인자로 받아서 해당 값 부터 반복문을 돌도록 해주면 이전에 고른 숫자보다 큰 숫자를 고르는 방식으로 조합을 구할 수 있다. 

- 선택한 숫자의 좌표를 구한 뒤에 해당 좌표가 이다솜파면 sCount를 증가시켜주었다.

- 7명을 선택했을 때, 이다솜파가 4명 이상이면 해당 조합으로 bfs를 실행시킨다.  

let arr = new Array(7);

const permutation = (at, count, sCount) => {
    if (count === 7) {
        if (sCount >= 4) bfs([...arr]);
        return;
    }

    for (let i = at; i < 25; i++) {
        arr[count] = i;
        const isSom = board[Math.floor(i / 5)][i % 5] === "S" ? 1 : 0;
        permutation(i + 1, count + 1, sCount + isSom);
    }
};

 

(2) 조합이 모두 이어져있는지 bfs도 확인하기 

- 보통 bfs에서는 좌표 내에서 상하좌우를 탐색하고 해당 상하좌우에 원하는 값이 있으면 큐에 넣는 방식으로 사용된다. 하지만 이번 bfs에서는 리스트의 값들이 서로 이어져있는지 확인하고 싶은 것이므로, 상하좌우를 탐색하고, 해당 값이랑 리스트에 있는 값이랑 일치하는 것이 있는지 확인 하는 방법을 사용해주었다. 

- 5*5 배열을 생성해서 좌표에 true 처리를 하고 상하좌우에 true인 위치가 있는지 확인하면 간편할 것 같지만 메모리를 너무 많이 사용하기 때문에 리스트 반복을 도는 for문을 추가해서 풀게 되었다. 

const node = queue[idx++]; // 조합에서 선택된 숫자 (1~25) 
const x = Math.floor(node / 5); // 숫자를 사용해서 x 좌표 구하기
const y = node % 5; // y 좌표 구하기

for (let i = 0; i < 4; i++) {
    const nx = x + dx[i]; // 상하좌우 확인하기 
    const ny = y + dy[i];
  
    for (let j = 1; j < 7; j++) { // 리스트에 있는 좌표들과 상하좌우 좌표들 일치하는지 확인하기
        const next = list[j];  
        const nextX = Math.floor(next / 5);
        const nextY = next % 5;

        if (!visited[j] && nx == nextX && ny === nextY) { // 방문하지 않았고, 좌표 일치하면
            visited[j] = true;
            queue.push(list[j]); // 큐에 추가하기
            count++; 
        }
    }
}

 

✅ 성공