-
문제
https://www.acmicpc.net/problem/14889
How to Solve ?
이 문제를 풀어 보기 전에 15649 - N과 M(1) 을 풀어본다면 백트래킹을 푸는데 용이 할 것이다. 필자가 푼 문제의 링크를 추후에 공유 해둘테니 DFS, BFS의 맛을 본 학습자라면 이 기회를 통해 "백트래킹"을 학습 해보길 !
https://kimbangg.tistory.com/207
[1] 백트래킹
백트래킹이란, DFS의 특징을 유지하지만 "필요 없다고" 판단되는 길은 가지 않도록 설정한 알고리즘이다.
스타트와 링크의 예시를 보면, 4가 주어졌을 때 스타트 팀이 구성 될 수 있는 경우는
[1,2] [1,3] ,[1,4] .. [2,1] [2,3] 등 인데, 백트래킹이 아닌 DFS만을 사용 한다면 [1,1] [2,2] 과 같은 중복 값이 나올 수도 있다.
1) 그리하여 아래의 코드를 통해서, 수열의 값들을 추가 해주고,
for (let i = 0; i < N; i++) { if (visited[i] === 1) continue; visited[i] = 1; start.push(i + 1); dfs(index + 1); start.pop(); visited[i] = 0; }
2) 다음과 같이 설정 해놓은 길이에 맞는 수열이 오면 ( [1,2], [1,3] .. )
const half = Math.floor(N/2); if (index === half) { }
3) 주어진 정보를 통해, 팀을 구성 + 점수 차이를 구한다.
if (index === half) { let startSum = 0; let linkSum = 0; for (let i = 1; i <= N; i++) { if (start.indexOf(i) === -1) { link.push(i); } } for (let j = 0; j < half - 1; j++) { for (let k = j + 1; k < half; k++) { startSum += point[start[j] - 1][start[k] - 1] + point[start[k] - 1][start[j] - 1]; linkSum += point[link[j] - 1][link[k] - 1] + point[link[k] - 1][link[j] - 1]; } } let diff = Math.abs(linkSum - startSum); if (min > diff) { min = diff; } link = []; return; }
전체 코드
function dfs(index) { // 원하는 인덱스, 배열의 크기가 됬을 때 etc) [1,2].. if (index === half) { let startSum = 0; let linkSum = 0; // 인덱스 값 -1 == 스타트팀 안에 없는 숫자임을 의미. for (let i = 1; i <= N; i++) { if (start.indexOf(i) === -1) { link.push(i); } } // 스타트와 링크 팀의 값을 더한다. for (let j = 0; j < half - 1; j++) { for (let k = j + 1; k < half; k++) { startSum += point[start[j] - 1][start[k] - 1] + point[start[k] - 1][start[j] - 1]; linkSum += point[link[j] - 1][link[k] - 1] + point[link[k] - 1][link[j] - 1]; } } let diff = Math.abs(linkSum - startSum); if (min > diff) { min = diff; } link = []; return; } // 수열을 만들기 위한 백트래킹 for (let i = 0; i < N; i++) { if (visited[i] === 1) continue; visited[i] = 1; start.push(i + 1); dfs(index + 1); start.pop(); visited[i] = 0; } } // local test const N = 4; const point = [ [0, 1, 2, 3], [4, 0, 5, 6], [7, 1, 0, 2], [3, 4, 5, 0], ]; const start = []; let link = []; const half = Math.floor(N / 2); const visited = Array(N).fill(0); let min = Infinity; dfs(0); console.log(min);
'PS > 백준' 카테고리의 다른 글
[백준_1343] 폴리오미노 ( 그리디 - 자바스크립트 ) (0) 2021.06.11 [백준_15649] N과 M(1) [ 백트래킹(기초) - 자바스크립트 ) (0) 2021.06.10 [백준_1911] 흙길 보수하기 ( Greedy - 자바스크립트 ) (0) 2021.06.10 [백준_1182] 부분 수열의 합 ( dfs - 자바스크립트 ) (0) 2021.06.09 [백준_2018] 수들의 합5 ( 투포인터 - 자바스크립트) (0) 2021.06.09 댓글