[백준] 1941_소문난 칠공주 (Javascript)

문제

BOJ1941_소문난 칠공주

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./Javascript/input.txt";
const students = require("fs").readFileSync(filePath).toString().trim().split("\n");
const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];
const combination = [];
let answer = 0;

// 7명의 여학생 조합이 만들어졌다면 BFS로 이 여학생들이 전부 인접해있는지 확인한다.
function bfs(combination) {
    // 모든 위치를 방문처리 해준다. (true로 초기화)
    const visited = Array.from({ length: 5 }, () => Array(5).fill(true));
    // 조합에 속해있는 여학생의 위치는 방문 처리를 해제 해준다.
    for (const [y, x] of combination) {
        visited[y][x] = false;
    }
    // BFS 시작
    const queue = [combination[0]];
    visited[combination[0][0]][combination[0][1]] = true;
    let visitCount = 1;
    let front = 0;
    while (queue.length > front) {
        let [y, x] = queue[front++];
        for (let i = 0; i < 4; i++) {
            let ny = y + dy[i];
            let nx = x + dx[i];
            // 범위를 벗어나지 않고 방문한 적 없는 위치일 경우
            if (ny >= 0 && nx >= 0 && ny < 5 && nx < 5 && !visited[ny][nx]) {
                visited[ny][nx] = true;
                visitCount++;
                queue.push([ny, nx]);
            }
        }
    }
    // 7명 모두 인접해있을 경우 true 반환
    return visitCount === 7;
}

// 우선 인접한지 여부 상관없이 7명이 모일수 있는 조합을 전부 구한다. (임도연파가 4명 이상 속해있는 경우는 빼고)
function dfs(cur, countY) {
    // 임도연파가 4명 이상일 경우
    if (countY >= 4) return;
    // 7명이 모였을 경우
    if (combination.length === 7) {
        if (bfs(combination)) answer++;
        return;
    }
    for (let i = cur; i < 25; i++) {
        let y = Math.floor(i / 5); // 행
        let x = i % 5; // 열
        // 현재 학생의 위치 추가
        combination.push([y, x]);
        // 재귀 호출
        dfs(i + 1, countY + (students[y][x] === "Y" ? 1 : 0));
        // 재귀 탈출하면 배열의 마지막 요소 제거(pop)
        combination.pop();
    }
}

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

코드 설명

1. 우선 DFS로 인접해있는지 여부와 상관없이 7명이 만들어지는 경우를 전부 탐색하며 각각의 학생의 위치를 combination 변수에 저장한다.
2. 만약 7명이 만들어졌을 경우 BFS로 그 7명이 전부 인접해있는지 확인하고 만약 전부 인접해 있다면 카운트를 증가시킨다.

2번의 경우에는 BFS를 사용하든 DFS를 사용하든 상관없다. 왜냐하면 조합의 속한 여학생을 제외한 모든 학생의 위치는 전부 방문처리 하고 탐색을 시작하기 때문이다.

dfs() 함수 내부의 반복문에서는 i를 cur 부터 25까지 증가하도록 설정해놓았다.

i 가 cur 부터 시작하는 이유는 조합 가능한 여학생을 찾을 때 i 를 0부터 시작한다면 dfs를 재귀 호출할 때마다 매번 0번 인덱스에 있는 학생부터 탐색하기 때문에 이미 combination 변수에 저장되어 있는 학생이 또다시 저장되는 문제가 발생한다.

또한 2중 for문을 이용하지 않고 5*5인 25까지 점차 증가하도록 만든 이유는 cur을 1씩 증가시키기 편하기 때문이다.

후기

처음에 작성한 코드는 아래와 같다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./Javascript/input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");
const visited = Array.from({ length: 5 }, () => Array(5).fill(false));
let answer = 0;

function dfs(x, y, countY, countS) {
    // 범위를 벗어나거나 이미 방문한 학생일 경우
    if (x < 0 || y < 0 || x >= 5 || y >= 5 || visited[x][y]) return;
    else {
        visited[x][y] = true; // 방문
        if (input[x][y] === "Y") countY += 1; // 현재 학생이 임도연파일 경우
        else countS += 1; // 현재 학생이 이다솜파일 경우

        // 임도연파가 3명을 초과할 경우
        if (countY > 3) {
            visited[x][y] = false;
            return;
        }

        // 7명이 되었을 경우
        if (countY + countS === 7) {
            answer += 1;
            visited[x][y] = false;
            return;
        }

        dfs(x + 1, y, countY, countS);
        dfs(x - 1, y, countY, countS);
        dfs(x, y + 1, countY, countS);
        dfs(x, y - 1, countY, countS);
        visited[x][y] = false;
    }
}

for (let i = 0; i < 5; i++) {
    for (let j = 0; j < 5; j++) {
        dfs(i, j, 0, 0);
    }
}
console.log(answer);

처음엔 그냥 보통의 DFS로 코드를 작성했는데 아래와 같이 T자 모양인 경우를 고려하지 못하는 문제가 있었다.

.....
SYSYS
.Y...
.S...
.....

그래서 다른 분의 블로그를 참고했다. 이 블로그는 파이썬으로 코드를 작성했는데, 가독성이 좋아서 이 분의 블로그를 참고했다.

참고 블로그: https://ji-gwang.tistory.com/379