[Baekjoon] 24447_알고리즘 수업 - 너비 우선 탐색 4

Silver II

문제(출처: https://www.acmicpc.net/problem/24447)

---

< 알고리즘 수업 - 너비 우선 탐색 4 >

 

문제 풀이

 

bfs로 탐색하면서 노드의 깊이와 방문 순서를 저장해 준다.

여기서 중요한 점은 노드의 깊이와 방문 순서, 결과 값을 저장할 때 long 값으로 선언해 줘야 에러가 발생하지 않는다.

 

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _24447_ {
	static ArrayList<ArrayList<Integer>> arr;
	static long t[], d[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		int r=Integer.parseInt(st.nextToken())-1;
		
		arr=new ArrayList<>();
		t=new long[n];
		d=new long[n];
		
		for(int i=0; i<n; i++) {
			arr.add(new ArrayList<>());
			d[i]=-1;
		}
		
		for(int i=0; i<m; i++) {
			st=new StringTokenizer(bf.readLine());
			int a=Integer.parseInt(st.nextToken())-1;
			int b=Integer.parseInt(st.nextToken())-1;
			arr.get(a).add(b);
			arr.get(b).add(a);
		}
		
		for(int i=0; i<n; i++) {
			Collections.sort(arr.get(i));
		}
		
		d[r]=0;
		t[r]=1;
		bfs(r);
		
		long result=0;
		for(int i=0; i<n; i++) {
			result+=d[i]*t[i];
		}
		System.out.println(result);
	}

	private static void bfs(int r) {
		Queue<Integer>queue=new LinkedList<>();
		queue.add(r);
		long t_num=t[r];
		
		while(!queue.isEmpty()) {
			int num=queue.poll();
			for(int i=0; i<arr.get(num).size(); i++) {
				int temp=arr.get(num).get(i);
				if(d[temp]==-1){
					d[temp]=d[num]+1;
					t[temp]=++t_num;
					queue.add(temp);
				}
			}
		}
	}
}

 

Main

- 정점의 수 (n), 간선의 수 (m), 시작 정점 (r) 입력

- arr : 인접 리스트

   t:  노드의 방문 순서

   d : 노드의 깊이 (방문 여부를 확인하기 위해 -1로 초기화)

- 양방향으로 그래프 저장 후 오름차순을 위해 정렬

- 시작 정점의 노드의 깊이는 0이고 노드의 방문 순서는 1로 초기화 후 bfs 함수 호출

- result : 모든 노드에 대한 노드의 방문 순서 x 노드의 깊이

 

bfs(시작 정점 r)

- queue에 시작 정점 추가 및 노드의 방문 순서를 위해 초기값 저장

- queue가 빌 때까지 반복 -> 인접 정점의 수만큼 반복 -> 노드의 깊이가 -1이면 아직 방문하지 않았다는 뜻이므로 노드의 깊이 저장 및 노드의 방문 순서 저장 후 queue에 추가

* 노드의 깊이는 전 노드의 깊이 +1이다.

 

---

마무리🤔

 

long 값 범위 때문에 틀렸었다...

 

---