백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 15686 , 치킨 배달 [DFS]

백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 15686 , 치킨 배달 [DFS]

 

 

 

풀이 시간

 

 

 

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
참 BFS로 풀렸으면 좋았을텐데... 아쉽다. 시간 초과 때문에 통과 못했다.
처음에 치킨집을 기준으로 탐색을 해서 삽질하는데 시간을 많이 썼다. 이후 BFS로 어떻게든 풀려는 고집때문에 계속 시도해서 코드를 완성 시켰지만 막상 돌려보니 시간 초과가 난다. 허무.....
오히려 이 문제는 간단하게 좌표값 차이만으로만 구해주면 훨씬 간단히 풀리긴 하는 문제다.
다른 풀이들이 다 이런식으로 풀어서 나는 다르게 접근해서 풀고 싶었는데 시간복잡도 차이에서 애초에 불가했나보다.

 

문제 출처

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

15686번: 치킨 배달

 

 

 

 

 

 

 

풀이

 

 

이 문제를 통해 배운 것.

1. 기준을 잘세우자. 집들을 기준으로 했어야 했는데 치킨집을 기준으로 삼았던게 큰 실수 였다.

치킨집을 기준으로 삼으면 안되는 문제는 바로 2개 이상의 치킨집에서 거리를 계산할때 가장 가까운 집을 한 번에 정의하기 어렵다.

 

첫번째 치킨집과 거리를 계산한 집이 다음 두번째 치킨집과의 거리가 더 짧게 된다면 이걸 구분해주기가 어렵다.

필요 이상의 코드들이 생길 확률이 크다.

 

 

 

2. BFS로 접근한 것. BFS로 접근하면 필요하지 않은 좌표들까지 모두 탐색을 하기 때문에 시간복잡도가 늘어난다. 이 문제는 애초에 정해져 있는 좌표에서 정해져있는 좌표까지의 거리만 계산하면 되기 때문에 좌표-좌표 의 절댓값으로 계산해주는 방법으로 접근을 해야한다.

 

 

 

 

시간초과 코드

 

 

대충 코드 설명을 해보면

 

1. 치킨집 위치들을 따로 저장해준뒤 0으로 바꿔 준다.

2. 이후 조합을 통해 치킨집의 경우의 수들을 확인해주고 확인할 치킨집의 위치들만 2로 바꿔준다.

3. 이후 BFS를 통해 집을 기준으로 가장 가까운 치킨집들을 찾아 합을 계산해주었다.

 

 

코드들은 잘 돌아가나, 시간초과 발생으로 통과할 수 없다.

 

 

---

 

 

이후 풀이는 BFS 함수를 삭제하고 좌표값의 절댓값 차이만 계산해주는 코드로 변경하였다.

 

이 코드가 훨씬 빠르고 간결한 코드라 할 수 있겠다. 

 

 

 

 

https://velog.io/@ywc8851/%EB%B0%B1%EC%A4%80-15686-%EC%B9%98%ED%82%A8-%EB%B0%B0%EB%8B%AC-javascript

[백준] 15686 치킨 배달 - javascript

 

위 블로그를 참조하여 풀이를 진행하였다.

 

 

 

 

 

정답

 

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

const [N, M] = input.shift();
const MAP = input;

function solution(N, M, MAP) {
  let chicken = [];
  let house = [];
  for (let i = 0; i < N; i++)
    for (let j = 0; j < N; j++) {
      if (MAP[i][j] === 2) {
        chicken.push([i, j]);
      } else if (MAP[i][j] === 1) house.push([i, j]);
    }
  const getDist = (arr, [x, y]) => {
    let MIN = Infinity;
    arr.map((v) => {
      let [CX, CY] = chicken[v];
      MIN = Math.min(MIN, Math.abs(CX - x) + Math.abs(CY - y));
    });
    return MIN;
  };

  let answer = Infinity;
  let combination = new Array(chicken.length).fill(false);
  const check = (idx, cnt) => {
    if (cnt === M) {
      let result = [];
      let total = 0;
      for (let i = 0; i < chicken.length; i++)
        if (combination[i] === true) result.push(i);
      house.map((v) => (total += getDist(result, v)));
      answer = Math.min(answer, total);
      return;
    }
    for (let i = idx; i < chicken.length; i++) {
      if (combination[i] === true) continue;
      combination[i] = true;
      check(i, cnt + 1);
      combination[i] = false;
    }
  };

  check(0, 0);
  return answer;
}

console.log(solution(N, M, MAP));