白駿2644号:計数
24629 ワード
問題の説明
方法
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;
해당 위치 방문처리
해당 위치 큐에 더하기
}
}
}
}
以下の図が存在する場合は、1から開始することを考慮します.
1の値をとり、アクセス可能な場所を決定します.
2,3,4にアクセスできるので、キューに2,3,4を入れます.
while(--size 1>=0)終了後、キュー:[2,3,4]//size 2=3
2、3、4を取り出してアクセス可能な場所を決定します.
5,6,7,8にアクセスできるので、キューに5,6,7,8を入れます.
while(--size 2>=0)が終了すると、キュー:[5,6,7,8]//size 3=4
5、6、7、8を取り出して、アクセス可能な場所を決定します.
アクセスできる場所がないのでqは空になり、外のドアは閉まっています.
正解
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;
}
}
Reference
この問題について(白駿2644号:計数), 我々は、より多くの情報をここで見つけました https://velog.io/@qwerty1434/백준-2644번-촌수계산テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol