백준 15686 < 치킨 배달 > JavaScript

2022. 11. 24.·☕️ 커리어 & 인터뷰 준비/코딩 테스트

📍문제 링크

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

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

 

📍알고리즘 분류

- 구현

- 브루트포스

- 백트래킹

 

📍문제 풀이

- N * N 크기의 좌표 평면에서 2인 좌표가 최소 M개, 최대 N * N - 1 개, 1 도 몇 개 주어진다.

- 1인 좌표를 모두 순회하면서 2인 좌표까지의 맨해튼 거리의 총 합이 최소가 되는 것을 도출하면 된다.

 

- 2인 좌표값이 있는 배열을 백트래킹해나가야 하고, 순서는 상관없다 (조합)

 

- 맨해튼 거리의 총 합이 최소가 되려면 당연히 각 거리가 최소이어야 한다.

- 이를 구하려면 모든 2인 좌표 중에서 백트래킹으로 M개 만큼 고른 2인 좌표를 모두 탐색해서, 이 중에서 최솟값을 구해야 할 것이다. (이래서 브루트포스 태그가 붙은건가 싶다)

 

📍의사 코드

1. 좌표 평면을 2차원 배열로 만들고 1인 좌표값들, 2인 좌표값들을 배열로 추출한다.

2. 2 좌표값 배열에서 M개를 뽑는 경우의수를 실행 (조합) -> 오름차순 깨지면 가지치기하는 백트래킹 방식으로 조합 구현

3. 갯수가 M에 도달 (추출 완료)하면 1 좌표값 배열을 순회하며 최소 거리를 골라 합을 구성

4. 이를 반복하며 최솟값인 합을 출력

 

📍코드 (JavaScript)

const [in1, ...in2] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');
const [N, M] = in1.split(' ').map(Number);
const map = in2.map((el) => el.split(' ').map(Number));
// 치킨집 좌표를 저장하는 배열
const chickenPos = [];
// 일반집 좌표를 저장하는 배열
const housePos = [];
// 좌표 추출
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (map[i][j] === 2) chickenPos.push([i, j]);
    if (map[i][j] === 1) housePos.push([i, j]);
  }
}

const isUsed = [];
// 조합을 저장할 배열 (계속 업데이트됨)
const comb = [];
const answer = [];
// 치킨 거리를 계산하는 함수
const distanceCheck = (x, y) => {
  return Math.abs(x[0] - y[0]) + Math.abs(x[1] - y[1]);
};

const recursive = (depth) => {
  if (depth === M) {
    let sumDistance = 0;
    for (let house of housePos) {
      let minDistance = Infinity;
      for (let chicken of comb) {
        minDistance = Math.min(distanceCheck(house, chicken), minDistance);
      }
      sumDistance += minDistance;
    }
    answer.push(sumDistance);
    return;
  }

  for (let i = 1; i <= chickenPos.length; i++) {
    if (!isUsed[i]) {
      // 좌표값들이 왼쪽에서 오른쪽, 위에서 아래 방향 순이 되도록
      // 오름차순을 정의하기 위해, x좌표가 y좌표보다 작도록,
      // x좌표와  y좌표가 같으면 y좌표는 x 좌표보다 작아야 함
      if (
        depth > 0 &&
        (comb[depth - 1][0] > chickenPos[i - 1][0] ||
          (comb[depth - 1][0] === chickenPos[i - 1][0] &&
            comb[depth - 1][1] > chickenPos[i - 1][1]))
      )
        continue;
      comb[depth] = chickenPos[i - 1];
      isUsed[i] = true;
      recursive(depth + 1);
      isUsed[i] = false;
    }
  }
};

recursive(0);
console.log(Math.min(...answer));

 

📍리뷰

- 첫 번째 에러 : 중복된 값 나옴

수가 아닌, 좌표값을 비교하도록 해서 가지치키 조건 변경하여 해결

- 두 번째 에러 : 테케는 맞는데 칼오답

// 반례
5 4
2 1 0 1 2
0 0 0 0 0
0 0 2 0 0
0 0 0 0 0
2 1 0 1 2

ans: 4
내 답 : Infinity

 

최종출력값부터 거슬러올라가다보니 가지치기 조건이 또 잘못됐었음

인접한 위치에서 x, y 좌표값 같은 경우 y는 작게 수정

 

📍리팩토링

절대값을 구할 때 Math.abs() 메서드를 써서 코드를 단축

가지치기 조건없이 모든 경우를 살피는게 시간은 더 빠름 20ms 정도

하지만 가지치기 조건을 부여하는게 백트래킹이기 때문에 연습할때는 중복없도록 하자

'☕️ 커리어 & 인터뷰 준비/코딩 테스트' 카테고리의 다른 글
  • 백준 9251 < LCS > JavaScript
  • 백준 20291 < 파일 정리 > JavaScript
  • 백준 6603 < 로또 > JavaScript
  • 백준 16165 < 걸그룹 마스터 준석이 > JavaScript
지식물원
지식물원
지식이 자라는 식물원!
  • 지식물원
    지식물원
    지식물원
  • 전체
    오늘
    어제
    • 분류 전체보기 (512) N
      • 🎨 프론트엔드 공부 (249) N
        • JS & TS (88) N
        • HTML & CSS (22)
        • React & Next (49)
        • Vue & Nuxt (22)
        • 기타 (68)
      • 🤓 기술 학습 & 공부 기록 (116)
        • Node.js (0)
        • Python (37)
        • 백엔드 (0)
        • 딥러닝 (1)
        • 컴퓨터 일반 (72)
        • 개발 인프라 (6)
      • 👨‍💻 프로젝트 경험 (6)
        • Work (0)
        • Toy (6)
      • ⚙️ 개발 팁 & 노하우 (21)
        • 프론트엔드 (6)
        • 기타 (15)
      • ☕️ 커리어 & 인터뷰 준비 (88)
        • 코딩 테스트 (88)
      • 📰 기술 트렌드 & 생각 정리 (4)
      • 📚 기타 (25)
        • 마케팅 (15)
        • 비개발서적 (10)
  • 블로그 메뉴

    • 태그
  • 링크

  • 공지사항

    • 모바일 접속 시 코드 하이라이팅 깨질 때
  • 인기 글

  • hELLO· Designed By정상우.v4.10.3
지식물원
백준 15686 < 치킨 배달 > JavaScript
상단으로

티스토리툴바