[백준] 24444번 알고리즘 수업 - 너비 우선 탐색 1 JAVA (자바) 풀이
문제 24444번 (bfs)
: N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)
정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다
정점 R에서 시작하여 노드의 방문 순서를 출력하자
인접 정점은 오름차순으로 방문한다
bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점
for each v ∈ V - {R}
visited[v] <- NO;
visited[R] <- YES; # 시작 정점 R을 방문 했다고 표시한다.
enqueue(Q, R); # 큐 맨 뒤에 시작 정점 R을 추가한다.
while (Q ≠ ∅) {
u <- dequeue(Q); # 큐 맨 앞쪽의 요소를 삭제한다.
for each v ∈ E(u) # E(u) : 정점 u의 인접 정점 집합.(정점 번호를 오름차순으로 방문한다)
if (visited[v] = NO) then {
visited[v] <- YES; # 정점 v를 방문 했다고 표시한다.
enqueue(Q, v); # 큐 맨 뒤에 정점 v를 추가한다.
}
}
}
[입력]
: 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)
: 다음 M개 줄에 간선 정보 u v (가중치 1인 양방향 간선) (1 ≤ u < v ≤ N, u ≠ v)
모든 간선의 (u, v) 쌍의 값은 서로 다르다
[출력]
: 첫째 줄부터 N개의 줄에 방문 순서를 출력 (시작 정점에서 방문할 수 없는 경우 0을 출력)
[설명]
1. count를 통해 인덱스 추출
2. 오름차순 Collections.sort() 사용할 것
- for(){ bfs } 하지말 것 (bfs 메서드 내에서 큐에 계속 추가하면서 반복하면 된다)
- bfs메서드 내에서 다시 bfs를 호출하지 말 것 (백트래킹이나 dfs와는 다르다)
[코드]
import java.io.*;
import java.util.*;
public class Main{
static boolean visit[];
static int N,M,R,u,v,result[];
static ArrayList<Integer> arr[];
static int count =1;
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
arr=new ArrayList[N+1];
visit = new boolean[N+1];
result = new int[N+1];
for(int i=1; i<=N; i++){
arr[i]=new ArrayList<>();
}
while(M-->0){
st = new StringTokenizer(br.readLine());
u = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
arr[u].add(v);
arr[v].add(u);
}
for(int i=1; i<=N; i++){
Collections.sort(arr[i]);
}
bfs(R);
for(int i=1; i<=N; i++){
System.out.println(result[i]);
}
}
static void bfs(int start){
Queue<Integer> q = new LinkedList<>();
q.add(start);
visit[start]=true;
result[start]=count++;
while(!q.isEmpty()){
int p = q.poll();
for(int i=0; i<arr[p].size();i++){
int next = arr[p].get(i);
if(!visit[next]){
q.add(next);
visit[next]=true;
result[next]=count++;
}
}
}
}
} [해설]
: static boolean visit[];
static int N,M,R,u,v,result[];
static ArrayList<Integer> arr[];
static int count =1; count를 1로 초기화
: BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
arr=new ArrayList[N+1];
visit = new boolean[N+1];
result = new int[N+1];
: for(int i=1; i<=N; i++){
arr[i]=new ArrayList<>();
}
: while(M-->0){
st = new StringTokenizer(br.readLine());
u = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
arr[u].add(v); 양방향이라 양쪽으로 추가
arr[v].add(u); 양방향이라 양쪽으로 추가
}
: for(int i=1; i<=N; i++){
Collections.sort(arr[i]); 오름차순 정렬
}
: bfs(R); 시작 정점에서 bfs 돌리기
: for(int i=1; i<=N; i++){
System.out.println(result[i]); result 배열 출력
}
: static void bfs(int start){
Queue<Integer> q = new LinkedList<>(); 큐 선언
q.add(start); 큐에 시작 노드 추가
visit[start]=true; 시작노드 방문
result[start]=count++; count 추가
while(!q.isEmpty()){
int p = q.poll(); 큐에서 뽑기
for(int i=0; i<arr[p].size();i++){ 연결된 노드 개수만큼 반복
int next = arr[p].get(i); 연결된 노드들 뽑기
if(!visit[next]){ 방문하지 않았으면
q.add(next); 큐에 추가
visit[next]=true; 방문처리
result[next]=count++; count 증가
}
}
}
}
이제 풀어보러 갈께요 :)
https://www.acmicpc.net/problem/24444
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *