백준 2644번: 촌수계산
문제 설명
- 촌수관계를 그래프로 나타낼 수 있습니다.
- 두 사람의 그래프상의 거리를 구하는 문제입니다.
접근법
- 데이터가 인접리스트로 주어졌기 때문에 HashMap을 활용했습니다.
- 가중치가 없는 그래프의 거리는 BFS의 depth로 구할 수 있습니다.
pseudocode
main(){
AddToMap();입력 데이터를 활용해 HashMap을 만듭니다.
if(BFS가 target을 찾았으면){
몇번만에 찾았는지를 출력합니다.
}else{ // 타겟을 못찾았으면
-1을 출력합니다.
}
}
AddToMap(a,b,HashMap){
// 양방향 그래프이기 때문에 a가 key인 경우, b가 key인경우를 모두 입력해줘야 합니다.
// a를 key로 쓰는 경우
if(HashMap의 key에 a가 없으면){
HashMap에 key와 value가 (a,[b])인 값을 추가해라.
}else{ // HashMap의 key에 a가 있으면
HashMap의 a값([num1,num2...])에 b를 추가해라 // -> a:[num1,num2,...b]
}
// b를 key로 쓰는 경우
if(HashMap의 key에 b가 없으면){
HashMap에 key와 value가 (b,[a])인 값을 추가해라.
}else{ // HashMap의 key에 b가 있으면
HashMap의 b값([num1,num2...])에 a를 추가해라 // -> b:[num1,num2,...a]
}
//아래 정답에서는 if(key값이 있으면)으로 코딩했습니다.
}
BFS(start,target){
q와 방문여부를 만듭니다.
처음 start값을 q에 넣고 방문처리 합니다.
while(q가 빌 때까지){
깊이를 1 증가시킵니다.
현재시점의 q 크기
while(현재시점의 q만큼만 꺼냅니다){
int now = q에서 꺼낸 값
for(q에서 꺼낸 값에서 갈 수 있는 위치){
if(해당 위치를 방문했으면) continue;
if(해당 위치가 내가 찾던 그 위치면) return true;
해당 위치 방문처리
해당 위치 큐에 더하기
}
}
}
}
- BFS의 너비는 큐의 변화를 생각하면 쉽습니다.
다음과 같은 그래프가 존재하며 1에서 시작하는 경우를 생각해 보겠습니다.
시작 시점의 큐 : [1] // size1 = 1
1의 값을 꺼내어 방문가능한 위치를 확인합니다.
2,3,4를 방문할 수 있기 때문에 큐에 2,3,4를 넣습니다.
while(--size1>=0)이 끝난 뒤 큐 : [2,3,4] // size2 = 3
2,3,4를 꺼내면서 방문 가능한 위치를 확인합니다.
5,6,7,8을 방문할 수 있기 때문에 큐에 5,6,7,8을 넣습니다.
while(--size2>=0)이 끝난 뒤 큐 : [5,6,7,8] // size3 = 4
5,6,7,8을 꺼내면서 방문 가능한 위치를 확인합니다.
방문할 수 있는 곳이 없기때문에 q가 비게되고 바깥쪽 while문이 종료됩니다.
정답
import java.util.*;
public class Main {
static int depth = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int start = sc.nextInt();
int target = sc.nextInt();
int m = sc.nextInt();
HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
for (int i = 0; i < m; i++) {
int a1 = sc.nextInt();
int a2 = sc.nextInt();
AddToMap(a1, a2, map);
}
if (BFS(start, target, map, N)) {
System.out.println(depth);
} else {
System.out.println(-1);
}
}
public static void AddToMap(int a1, int a2, HashMap<Integer, List<Integer>> map) {
//a1을 key값으로 검사합니다.
if (map.containsKey(a1)) { // a1이 key로 존재하면 -> ArrayList의 value를 가지고 있다는 의미입니다.
map.get(a1).add(a2); // a1의 value(ArrayList)에 a2를 추가합니다.
} else { // a1이 key로 존재하지 않으면 -> ArrayList가 아직 만들어지지 않았다는 의미입니다.
List<Integer> temp = new ArrayList<Integer>();
temp.add(a2);
map.put(a1, temp); // a1이 키, a2를 담은 ArrayList가 value입니다.
}
//a2를 key값으로 검사합니다. 바로 위 코드와 구조적으로 완벽히 동일합니다.
if (map.containsKey(a2)) {
map.get(a2).add(a1);
} else {
List<Integer> temp = new ArrayList<Integer>();
temp.add(a1);
map.put(a2, temp);
}
}
public static boolean BFS(int start, int target, HashMap<Integer, List<Integer>> map, int N) {
Queue<Integer> q = new LinkedList<Integer>();
boolean[] v = new boolean[N + 1]; // 사람을 1부터 표현했기 때문에 0번자리를 사용하지 않고 N+1칸을 만들었습니다.
// 처음 입력값을 큐에 추가 및 방문처리 합니다.
q.add(start);
v[start] = true;
while (!q.isEmpty()) { // 큐가 빌때까지 반복합니다.
//queue의 크기만큼의 while문을 하나 더 생성하면 이는 depth마다 끊어서 돌리겠다는 의미입니다.
depth++;
int size = q.size();
while (--size >= 0) {
int now = q.poll();
for (Integer i : map.get(now)) {
if (v[i]) continue; // i를 이미 확인했다면 넘깁니다.
if (i == target) return true;// i가 내가 찾는 사람이라면 BFS를 멈추고 true를 반환합니다.
// 계속해서 BFS를 진행합니다.
v[i] = true;
q.add(i);
}
}
}
//target을 찾지 못한 경우입니다.
return false;
}
}
Author And Source
이 문제에 관하여(백준 2644번: 촌수계산), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qwerty1434/백준-2644번-촌수계산저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)