촌수 계산
문제
우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.
여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.
입력
사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.
각 사람의 부모는 최대 한 명만 주어진다.
출력
입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.
예제 입력 1
9 7 3 7 1 2 1 3 2 7 2 8 2 9 4 5 4 6예제 출력 1
3출처
- Olympiad > 한국정보올림피아드 > KOI 1999 > 중등부 1번
- 문제의 오타를 찾은 사람: dkdsla12 YunGoon
- 빠진 조건을 찾은 사람: jh05013
알고리즘 분류
- BFS
해결한 코드
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").trim().split('\n');
var n = parseInt(input[0])
var questionNumbers = input[1].split(' ').map(element => element / 1)
var numberOfRelationships = parseInt(input[2])
var relationships = []
for (var i = 3; i < input.length; i++){
relationships.push(input[i].split(' ').map((element) => element / 1))
}
function makeVisitArray() {
var visit = []
for (var i = 0; i <= n; i++) {
visit.push(Array(n + 1))
}
for (var i = 0; i < relationships.length; i++) {
var current = relationships[i]
var p = current[0]
var c = current[1]
visit[p][c] = false
visit[c][p] = false
}
return visit
}
var visit = makeVisitArray()
function bfs(){
var q = []
var start = questionNumbers[0]
var destination = questionNumbers[1]
var count = 0
q.push({p: start, c: count})
var flag = false
while(q.length !== 0){
var current = q.shift()
if(current.p === destination) {
flag = true
count = current.c
break
}
for(let i=0; i<relationships.length; i++){
if(relationships[i].some(e=> e === current.p) && visit[relationships[i][0]][relationships[i][1]] === false){
visit[relationships[i][0]][relationships[i][1]] = true
visit[relationships[i][1]][relationships[i][0]] = true
var next = relationships[i]
if(next[0] === current.p){
count = current.c+1
q.push({p:next[1], c:count})
} else {
count = current.c+1
q.push({p:next[0], c:count})
}
}
}
}
if(!flag){
count = -1
}
return count
}
console.log(bfs())알고리즘
※ BFS를 활용한다.
BFS 구현을 위해 필요한 것?
✔ 방문 여부를 체크할 visit
✔ 다음 순회할 원소를 저장하고 꺼낼 큐1. 방문 여부를 체크할 visit 배열을 만든다.
- 입력으로 들어오는 부모 자식 관계에 따라 true or false로 체크할 것
👉🏻 따라서 2차원 배열의 형태로 만든다.
ex. [1, 2]visit[1][2] = false visit[2][1] = false2. BFS를 구현한다.
🚩 정점간에 관계가 있을 수도 없을 수도 있으므로 초기값이 false인 flag 변수를 만든다.
2-1. 큐를 만든다.
2-2. 시작 정점과 마지막 정점을 지정한다.
👉🏻 촌수 계산을 위해 입력되는 두 수. 예를 들면, 위 입력 예시에서[7, 3]에 해당한다.2-3. 촌수를 계산할 count를 만든다.
2-4. 큐에 시작하는 정점과 촌수를 push한다.
👉🏻 나는 object 형태로 push했다.{p: 7, c: 0}
// 대충 p는 point, c는 count라는 말
시작 정점의 촌수는 아직 계산되지 않았으므로, count의 초기값을 0으로 했다.2-5. 큐의 첫번째 원소를 빼내어 순회를 시작한다.
- (입력으로 들어온) 관계들 중 시작 정점이 속한 배열이 있는지 확인한다.
ex. 입력으로 들어온 관계들은 다음과 같다.relationships = [ [1, 2] [1, 3] [2, 7] [2, 8] [2, 9] [4, 5] [4, 6] ]
- 이 중 시작 정점이 속한 배열이 있는지 확인한다.
시작정점 ={p: 7, c: 0}relationships = [ [1, 2] [1, 3] [2, 7] <= 7이 있음 [2, 8] [2, 9] [4, 5] [4, 6] ]
visit[2][7]이false인지 확인한다.
만약 false가 맞으면
👉🏻 visit[2][7] = true && visit[7][2] = true 로 방문했음을 표시하고,
👉🏻[2, 7]중, (시작 정점) 7이 아닌 2와, 촌수를 계산해주어야 하므로, 시작 정점의 c에 + 1한 값인 1을
{p: 2, c: 1}로 만들어 큐에 push한다.
🚩 관계가 있다는 의미으로 flag = true를 해준다.
- 큐의 첫번째 원소를 빼내어 위 과정의 순회를 반복한다.
마지막 정점을 순회할 때까지 반복한다.
- 만약 관계가 전혀 없으면
🚩 즉 flag가 false라면 -1을 return 한다.3. BFS의 결과를 출력한다.
