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

Silver II

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

---

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

 

문제 풀이

 

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

 

 

 

 my solution (Java)

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

public class _24446_ { // 알고리즘 수업 - 너비 우선 탐색 3
	static ArrayList<ArrayList<Integer>> arr;
	static int d[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		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<>();
		d=new int[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);
		}

		d[r]=0;
		bfs(r);

		for(int i=0; i<n; i++) {
			bw.write(d[i]+"\n");
		}
		bw.flush();
	}

	private static void bfs(int r) {
		Queue<Integer>queue=new LinkedList<>();
		queue.add(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;
					queue.add(temp);
				}
			}
		}
	}
}

 

Main

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

- arr : 인접 리스트

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

- 양방향으로 그래프 저장 

- 시작 정점의 노드의 깊이는 0으로 초기화 후 bfs 함수 호출

- d 배열 출력

 

bfs(시작 정점 r)

- queue에 시작 정점 추가 

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

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

 

---

마무리🤔

 

---