-
문제
https://www.acmicpc.net/problem/2644
How to Solve ?
[1] BFS
특정 인원과의 촌수를 찾는 다는 것은, 어떻게 보면 최단거리로 갔을 때만 얻어 질 수 있는 개념 이라 생각하여 "BFS"를 사용했습니다.
[1-1] 인접 행렬 만들기
인접 리스트가 더 효과적이라고 생각은 하지만 행렬 구현에 익숙해져서 인접행렬을 makeConnection 함수를 통해 구현 하였습니다.
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 1, 1, 1], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[1-2] 촌수 계산
연결된 사람을 따라가면서, 만날 수 있는 경우에는 bfs를 할 때 마다 카운트를 올려준다.
만약, 끝까지 했음에도 결과를 얻지 못하면 "-1" 을 출력한다.
전체 코드
function makeConnection(n, relation) { const arr = Array.from(Array(n + 1), () => Array(n + 1).fill(0)); for (let i = 0; i < relation.length; i++) { const [prev, next] = relation[i]; arr[prev][next] = 1; arr[next][prev] = 1; } return arr; } function bfs(start, end, visited, connection, answer) { const queue = [start, 0]; visited[start] = 1; while (queue.length) { start = queue.shift(); let count = queue.shift(); // 원하는 인원과의 연결 고리를 찾으면 if (start === end) { answer = count; break; } else { // 인접 행렬을 순환하면서 자신과 연결된 가장 가까운 인원을 탐색 for (let i = 1; i <= n; i++) { // 방문한 기록이 없고, 연결이 되어 있으면 if (connection[start][i] === 1 && !visited[i]) { // 방문 처리를 해주고, visited[i] = 1; // bfs를 실행. queue.push(i, count + 1); } } } } return answer; } function solution(n, relation) { let answer = 0; const [a, b] = [7, 3]; const connection = makeConnection(n, relation); const visited = Array(n + 1).fill(0); answer = bfs(a, b, visited, connection, answer); // 반환된 값이 없다면, 연결고리가 없음을 의미 answer === 0 ? console.log(-1) : console.log(answer); } // local input // const n = 9; // const m = 7; // const relation = [ // [1, 2], // [1, 3], // [2, 7], // [2, 8], // [2, 9], // [4, 5], // [4, 6], // ]; // solution(n, relation);
'PS > 백준' 카테고리의 다른 글
[백준_1268] 임시 반장 정하기 ( 구현 - 자바스크립트 ) (0) 2021.06.28 [ 백준 _ 15271 ] 번데기 by using JavaScript (0) 2021.06.27 [ 백준 - 2659 ] 십자카드 문제 ( 완전탐색 - 자바스크립트 ) (0) 2021.06.27 [ 백준_16953 ] A -> B ( d/bfs - 자바스크립트 ) (0) 2021.06.25 [백준_1713] 후보 추천하기 ( 시뮬레이션 - 자바스크립트 ) (0) 2021.06.17 댓글