[JS] 소가 길을 건너간 이유6

그래프와 DFS를 활용한 풀이

 

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

14466번: 소가 길을 건너간 이유 6

 

 

 

소와 소를 만나는 과정을 DFS를 활용해서 구하되 가는 길에 다리가 있다면 건너지 않으면 된다.

 

1. 그래프 설정하기

2. 소를 1:1 대응으로 찾을 수 있는지 분리

3. 각 대응마다 DFS를 활용하여 소에서 소로 갈 수 있는지 확인

 

 

includes는 배열의 1차까지만 비교하기 때문에 find를 활용해서 찾아야 한다!

 

 

 

 

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map((v) => +v));

const [n, k, r] = input[0];

//그래프 생성
const graph = [...Array(n)].map((_) => [...Array(n)].map((_) => []));
for (let i = 1; i < r + 1; i++) {
  const [sr, sc, er, ec] = input[i].map((v) => v - 1);
  graph[sr][sc].push([er, ec]);
  graph[er][ec].push([sr, sc]);
}
//소 정보 저장
const cowInfo = [];
for (let i = r + 1; i < r + 1 + k; i++) {
  const [r, c] = input[i].map((v) => v - 1);
  cowInfo.push([r, c]);
}

const dr = [1, 0, -1, 0];
const dc = [0, 1, 0, -1];
//소-소로 갈수있는지 판별
const dfs = (ary, sR, sC, eR, eC) => {
  const stk = [[sR, sC]];
  ary[eR][eC] = "e";
  while (stk.length) {
    const [r, c] = stk.pop();
    if (ary[r][c] === 1) continue;
    if (ary[r][c] === "e") return true;
    ary[r][c] = 1;

    for (let d = 0; d < 4; d++) {
      const [nR, nC] = [r + dr[d], c + dc[d]];
      if (!(0 <= nR && nR < n && 0 <= nC && nC < n)) continue;
      if (graph[r][c].find((v) => v[0] === nR && v[1] === nC)) continue;
      stk.push([nR, nC]);
    }
  }
  return false;
};

let ret = 0;

//소의 경우의수 마다 갈 수 있는지 계산
for (let i = 0; i < cowInfo.length - 1; i++) {
  for (let j = i + 1; j < cowInfo.length; j++) {
    const [sR, sC] = cowInfo[i];
    const [eR, eC] = cowInfo[j];
    const cowMap = [...Array(n)].map((_) => Array(n).fill(0));
    ret += dfs(cowMap, sR, sC, eR, eC) ? 0 : 1;
  }
}
console.log(ret);