TIL

그래프 알고리즘 공부를 시작했다.
오늘은 BFS(Breadth-First Search), 너비 우선 탐색을 공부했다.

그래프

그래프는 현상이나 사물을 정점과 간선으로 표현한 것이다.
정점은 대상이나 개체를 나타내고 간선은 이들 간의 관계를 나타낸다.

간선이 방향을 가지면 유향 그래프라 하고 간선의 방향이 없으면 무향 그래프라고 한다.

너비 우선 탐색

그래프를 모두 방문하는 알고리즘에 너비 우선 탐색과 갚이 우선 탐색이 있는데, 오늘은 너비 우선 탐색을 공부했다.

너비 우선 탐색은 노드의 자식을 차례로 방문한다.
노드 1을 방문했으면 노드 1에 붙어있는 2,3,4를 차례로 먼저 방문하고
그 다음은 노드 2를 방문하여 노드 2에 붙어있는 5와 6을 방문,
노드 2의 자식을 모두 방문했으면 노드 3의 자식 방문..
이런식이다.

백준 24444번 알고리즘 수업 - 너비 우선 탐색 1

https://www.acmicpc.net/problem/24444

입력이
5 5 1
1 4
1 2
2 3
2 4
3 4

다음과 같이 주어지면
정점의 갯수는 5, 간선의 갯수는 5, 시작 정점은 1이고
간선 5개는 각각 (1,4) (1,2) (2,3) (2,4) (3,4) 이다.

그림을 그리면 이런 모양이다(발 그림 무시하세용)

i번째 줄에는 정점 i의 방문 순서를 출력한다.
방문해야하는 정점이 아무 간선과도 연결되어 있지 않으면 0을 출력하면 된다.

1. 1의 자식인 2와 4 방문.
2. 2의 자식인 3 방문
3. 5는 방문하지 못함

그러니 1 2 4 3 0을 출력하면 된다.

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.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class algorithm_class_24444 {
	
	static ArrayList<ArrayList<Integer>> graph;
	static int[] visited;
	static int N,M,R;
	StringTokenizer st;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken()); // 정점의 수
		M = Integer.parseInt(st.nextToken()); // 간선의 수
		R = Integer.parseInt(st.nextToken()); // 시작 정점

		visited = new int[N + 1];

		graph = new ArrayList<ArrayList<Integer>>();

		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
			
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			graph.get(a).add(b);
			graph.get(b).add(a);
		
		}

		for (int i = 1; i <= N; i++) {
			Collections.sort(graph.get(i));
		}
		
		bfs(R);

		for (int i = 1; i <= N; i++) {
			bw.write(visited[i] + "\n");
		}
		
		bw.flush();
		bw.close();
	}

	static void bfs(int start) {	
		int cnt = 1;
		
		Queue<Integer> q = new LinkedList<Integer>();

		q.offer(start);
		
		visited[start] = cnt++;
		
		while (!q.isEmpty()) {
			int nodeIndex = q.poll();
			//Collections.sort(graph.get(nodeIndex),Collections.reverseOrder()); //내림차순 정렬 24445번
			for (int i = 0; i < graph.get(nodeIndex).size(); i++) {
				int temp = graph.get(nodeIndex).get(i);
				if (visited[temp] != 0) {
					continue;
				}
				q.offer(temp);
				visited[temp] = cnt++;
			}
		}
	}
}

중간에 내림차순 정렬을 하면 24445번을 풀 수 있다.
https://www.acmicpc.net/problem/24445
1의 자식중에서 4부터 방문하는 결과를 볼 수 있다.

리스트에 간선이 넣어지는 모양이 이해가 안돼서 따로 출력을 해보았다.
리스트 1에 인접한 정점 2와 4가, 리스트 2에 인접한 정점 1,3,4 가 넣어져 있는 것을 확인할 수 있다.
이 리스트에 접근해서 자식을 하나하나 확인하고 방문했으면 visit의 cnt를 높이는 방식이다.
cnt는 방문한 순서이다.

그래프 부터 구현이 꽤 복잡해진다.
여러번 공부해야겠다.