[백준] 단계별로 풀어보기(단계:25, 그래프와 순회,JAVA)24445번, 알고리즘 수업 - 너비 우선 탐색 2

문제 링크

24445번: 알고리즘 수업 - 너비 우선 탐색 2

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

BFS

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

 

이 문제에 핵심은

1. 정점과 간선의 정보를 이용해서 출발 정점에서 각 정점을 방문하는 순번을 결과로 출력한다.

2. 간선은 무방향입니다.

3. 방문하지 않는 정점의 순번은 0으로 표현한다.

4. 정점 내림차순으로 너비 우선 탐색을 진행합니다.

 

그래프에 대한 내용을 정의하기 위해 ArrayList<ArrayList<Integer>>의 형태로 리스트를 만들어주었습니다.

위와 같이 정의하여 데이터를 저장하면 각 정점이 어떤 정점으로 이동하는지 간단하게 저장할 수 있습니다.

예를 들어 

1 -> 4

1 -> 3

2 -> 5

3 -> 4

 

ArrayList<ArrayList<Integer>>의 저장되는 모습은 리스트 안에 리스트가 포함되는 형식으로 저장됩니다.

정점
1	3	4
2	5
3	1	4
4	1	4
5	2

 

그래프의 값을 리스트에 저장하였다면 출발 정점에서 BFS탐색을 시작하여 방문하는 순번을 구하였습니다.

 

예제 입력1에서 첫 번째 테스트케이스의 그래프를 표로 확인하며 보여드리겠습니다.

아래는 예제로 주어진 그래프입니다.

그래프의 내용이 저장된 ArrayList<ArrayList<>>의 해당하는 표

정점
1	2	4
2	1	3	4
3	2	4
4	1	2	3
5

1. 시작 정점 1부터 너비 탐색을 진행합니다.

 

그래프 내용인 ArrayList<ArrayList<Integer>>을 이용하여 인접한 정점을 탐색합니다.

 

그래프에서 정점1과 인접한 정점을 내림차순으로 4, 2 탐색합니다.

 

2. 너비 우선으로 정점 4에서 인접한 정점 탐색합니다.

 

그래프에서 정점4와 인접한 정점은 1, 2, 3이지만

 

2는 탐색을 완료하거나 Queue에 이미 저장되어 있기 때문에

 

그래프에서 정점4와 인접한 정점을 3을 탐색합니다.

3. 너비 우선으로 정점 3에서 인접한 정점 탐색합니다.

 

그래프에서 정점3과 인접한 정점은 2, 4이지만

 

2, 4은 탐색을 완료하거나 Queue에 이미 저장되어 있기 때문에

 

현재 너비는 탐색 종료.

 

4. 너비 우선으로 정점 2에서 인접한 정점 탐색합니다.

 

그래프에서 정점3과 인접한 정점은 1, 3, 4이지만

 

1, 3, 4은 탐색을 완료하거나 Queue에 이미 저장되어 있기 때문에

 

현재 너비는 탐색 종료.

 

더 이상 이전 큐의 정점의 값이 존재하지 않기 때문에 너비 우선 탐색은 종료합니다.

 

각 과정에서 정점을 방문할 때 순서를 배열에 저장한 뒤 결과로 출력하였습니다.

 

문제를 해결한 알고리즘의 과정입니다.

 

1. 그래프에 대한 정보를 ArrayList<ArrayList<Integer>>에 저장합니다.

2. BFS(너비 우선 탐색)을 이용하여 시작정점 R에서 탐색을 시작합니다.

3. 각 정점을 방문할 때 방문한 순번을 배열에 저장합니다.

4. BFS탐색이 종료한 뒤 순번을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 그래프에 대한 정보를 저장하였습니다.
• 그래프에 내용 저장할 ArrayList<ArrayList<Integer>> graph를 만들었습니다.
• BFS로 그래프의 시작정점부터 탐색을 진행하는 bfs 함수를 만들었습니다.
• BufferedWriter에 BFS탐색으로 얻은 방문 순번을 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs은 visited[], graph와 Queue를 이용하여 방문 여부 확인과 순번을 배열에 저장 및 내림차순으로 탐색합니다.

결과 코드

import java.io.*;
import java.util.*;

public class Main {
	static int N,M,R,count=1;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();	//그래프 값 저장
	static int[] result;	//순번 저장 배열
	static boolean[] visited;	//방문 확인 배열
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //그래프 값 저장
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	R = Integer.parseInt(st.nextToken());
    	result = new int[N+1];
    	visited = new boolean[N+1];
    	for(int i=0;i<=N;i++)
    		graph.add(new ArrayList<>());
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		int u = Integer.parseInt(st.nextToken());
    		int v = Integer.parseInt(st.nextToken());
    		graph.get(u).add(v);
    		graph.get(v).add(u);
    	}
    	bfs(R);		//너비 우선 탐색 수행
    	for(int i=1;i<=N;i++)	//순번 BufferedWriter 저장
    		bw.write(result[i] + "\n");
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //너비 우선 탐색하는 함수
    static void bfs(int start) {
    	Queue<Integer> queue = new LinkedList<Integer>();
    	result[start] = count++;	//순번 저장
    	visited[start] = true;	//방문 확인
    	queue.add(start);
    	while(!queue.isEmpty()) {
    		int point = queue.poll();
    		Collections.sort(graph.get(point),Collections.reverseOrder());	//내림차순 정렬
    		for(int next : graph.get(point)) {	//인접 정점 탐색
    			if(!visited[next]) {	//방문했는지 확인
    				visited[next] = true;	//방문 확인
    				result[next] = count++;	//순번 확인
    				queue.add(next);
    			}
    		}
    	}
    	return;
    }
}