[JS][백준]15566_개구리 1

문제 번호

15566번: 개구리 1

 

 

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

 

문제 풀이

 입력이 길어서 당황했지만 문제를 읽어보면 백트래킹을 이용해서 브루트포스를 진행하면 풀 수 있다는 것을 알 수 있다. 처음에는 개구리들을 모두 배치하고 나서 DFS로 정답여부를 판별하려 했으나 그것보다는 개구리를 한마리 한마리 배치하면서 정답에 부합하는지 확인하는것이 더 적절하다고 판단했다.

 우선 연꽃이 비어있는지, 이미 개구리가 앉있는지 확인할 배열과 자리를 잡지 못한 개구리가 있는지 확인할 배열을 만든다.

function main() {
  let map = new Array(N).fill(-1); // 연꽃에 개구리가 있는지 확인할 배열.
  let stay = new Array(N).fill(false); // 자리를 잡지 못한 개구리들이 있는지 확인할 배열.
  sol(0, map, stay);
  console.log(answer);  
}

 

 이제 N마리의 모든 개구리가 자리를 잡았는지 확인해야한다. 백트래킹을 사용할 것이기 때문에 종료 조건으로 모든 개구리가 연꽃에 앉았을 때를 생각해준다.

  if (cnt === N) {
    answer = 'YES\n';    
    for(let print = 0; print < map.length; print++) {
      answer += map[print] + 1 + ' ';
    }
    console.log(answer);
    process.exit(0);
  }

 

 종료 조건이 아니라면 N마리의 개구리를 모두 확인해본다. 우선 i번째 개구리가 이미 연꽃에 앉아있는 개구리라면 다시 중복해서 확인할 필요가 없다.

      if (stay[i]) continue; // 이미 확인한 개구리면 통과한다.

 

 연꽃에 앉지 못한 개구리라면 그 개구리가 선호하는 연꽃의 번호를 확인해보자.

 for (let j = 0; j < favor[i].length; j++) { // i번째 개구리가 선호하는 연꽃들.
        let flower = favor[i][j]; // 선호하는 연꽃.
        flower--;

연꽃의 번호는 1번부터 시작하지만 인덱스는 0부터 시작하기때문에 flower 라는 변수를 1 만큼 줄여서 사용했다.

 

 선호하는 연꽃이 비어있다면 해당 연꽃과 통나무로 연결되어있는 모든 연꽃들을 cadidate라는 배열에 넣어본다.

          let candidate = [];
          for (let k = 0; k < wood.length; k++) { // 선호하는 연꽃과 연결된 연꽃을 찾아본다.
            let [A, B, T] = wood[k];
            A--; B--;
            if (flower === A || flower === B) // 선호하는 연꽃과 연결된 연꽃들을 집어 넣는다.
              candidate.push(wood[k]);
          }

 

 연결된 모든 연꽃을 배열에 집어넣었다면 대화 주제에 대한 흥미도가 일치하는지 확인해야한다. 연결된 연꽃에 다른 개구리가 앉아있다면 그 개구리와 대화 주제에 대한 흥미도가 일치하는지 확인해야한다. 만약 대화 주제에 대한 흥미도가 일치하지 않는다면 i 번째 개구리는 해당 선호연꽃에 앉을 수 없다.

          let check = true;
          for (let candi = 0; candi < candidate.length; candi++) { // 후보자들을 살펴본다.
            let [A, B, T] = candidate[candi];
            A--; B--;
            // 선호하는 연꽃과 연결된 연꽃에 있는 개구리들과 대화 흥미가 일치하는지 살펴본다.
            // 대화 흥미가 일치하지 않는경우만 확인한다.
            if (flower === A) {
              if (map[B] !== -1) {
                if (forgs[i][T - 1] !== forgs[map[B]][T - 1]) {
                  check = false;
                  break;
                }
              }
            }
            else if (flower === B) {
              if (map[A] !== -1) {
                if (forgs[i][T - 1] !== forgs[map[A]][T - 1]) {
                  check = false;
                  break;
                }
              }
            }
          }

 

 선호 연꽃과 연결된 연꽃이 비어있거나 연결된 연꽃에 앉은 개구리와 대화의 흥미도가 일치할 경우, i번째 개구리는 해당 선호 연꽃에 앉을 수 있다.

          if (check) {
            map[flower] = i;
            stay[i] = true;
            sol(cnt + 1, map, stay);
            map[flower] = -1;
            stay[i] = false;
          }

 

 위와 같이 백트래킹을 사용하여 모든 경우의 수를 탐색해도 시간제한에 걸리지 않고 문제를 해결 할 수 있다. 주의 할 점은 개구리와 연꽃은 1번부터 시작하지만 인덱스는 0번부터 시작하기 때문에 해당 숫자들을 잘 맞춰서 사용해줘야한다.

 

전체코드

//  1. 개구리 배치
//    개구리는 선호하는 연꽃에 배치되어야 한다.
//    2^15 가지의 방법으로 개구리를 배치할 수 있다. 
//    개구리를 배치할때 backtracking 으로 배치한다?
// 0번 개구리 부터 배치한다
// 배치했으면 0번 개구리가 놓여진 연꽃과 연결되어있는 노드를 선호하는 개구리를 찾는다.
// 이때 대화주제의 흥미도를 검사하여 놓을 수 있는지 확인한다.
// 놓을 수 있는 개구리가 없으면 backtracking 한다.


const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number); // 개구리, 통나무.
const forgs = input.slice(1, N + 1).map(_ => _.trim().split(' ').map(Number)); // 대화 흥미도.
const favor = input.slice(N + 1, N + 1 + N).map(_ => _.trim().split(' ').map(Number)); // 개구리의 선호 연꽃.
const wood = input.slice(N + 1 + N, N + 1 + N + M).map(_ => _.trim().split(' ').map(Number)); // 통나무와 대화주제.
let answer = 'NO';

function sol(cnt, map, stay) {
  if (cnt === N) {
    answer = 'YES\n';    
    for(let print = 0; print < map.length; print++) {
      answer += map[print] + 1 + ' ';
    }
    console.log(answer);
    process.exit(0);
  }
  else {
    for (let i = 0; i < N; i++) { // N 마리의 개구리를 확인해본다. 개구리는 0 번 부터 시작.
      if (stay[i]) continue; // 이미 확인한 개구리면 통과한다.
      for (let j = 0; j < favor[i].length; j++) { // i번째 개구리가 선호하는 연꽃들.
        let flower = favor[i][j]; // 선호하는 연꽃.
        flower--;
        if (map[flower] === -1) { // 선호하는 연꽃이 비어 있는 연꽃인가?          

          let candidate = [];
          for (let k = 0; k < wood.length; k++) { // 선호하는 연꽃과 연결된 연꽃을 찾아본다.
            let [A, B, T] = wood[k];
            A--; B--;
            if (flower === A || flower === B) // 선호하는 연꽃과 연결된 연꽃들을 집어 넣는다.
              candidate.push(wood[k]);
          }

          let check = true;
          for (let candi = 0; candi < candidate.length; candi++) { // 후보자들을 살펴본다.
            let [A, B, T] = candidate[candi];
            A--; B--;
            // 선호하는 연꽃과 연결된 연꽃에 있는 개구리들과 대화 흥미가 일치하는지 살펴본다.
            // 대화 흥미가 일치하지 않는경우만 확인한다.
            if (flower === A) {
              if (map[B] !== -1) {
                if (forgs[i][T - 1] !== forgs[map[B]][T - 1]) {
                  check = false;
                  break;
                }
              }
            }
            else if (flower === B) {
              if (map[A] !== -1) {
                if (forgs[i][T - 1] !== forgs[map[A]][T - 1]) {
                  check = false;
                  break;
                }
              }
            }
          }

          if (check) {
            map[flower] = i;
            stay[i] = true;
            sol(cnt + 1, map, stay);
            map[flower] = -1;
            stay[i] = false;
          }
        }
      }
    }
  }
  return;  // 모든 개구리를 살펴봤는데 적당한 개구리가 없으면 이전단계로 되돌아간다.
}

function main() {
  let map = new Array(N).fill(-1); // 연꽃에 개구리가 있는지 확인할 배열.
  let stay = new Array(N).fill(false); // 자리를 잡지 못한 개구리들이 있는지 확인할 배열.
  sol(0, map, stay);
  console.log(answer);  
}
main();

 

특이사항