백준 24444, 24480 알고리즘 수업 - 너비 우선 탐색 1,2 / JAVA

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

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

 

문제분석

예제 입력을 노드와 그래프로 나타내면 아래와 같다

5개의 노드지만 이동하는 간선이 없으므로 생략한다.

 

DFS와 마찬가지로 출력사항이 이해가 안되지만 억지로 구현까지 일단 해봤다..

 

입력값에 대한 그래프를 인접리스트로 나타내면 아래와 같다

arr[1] : [4, 2]
arr[2] : [1, 3, 4]
arr[3] : [2, 4]
arr[4] : [1, 2, 3]
arr[5] : []

 

문제에서 오름차순으로 정렬 후 탐색하라는 조건을 만족하기 위해 Collections.sort()를 사용 하면 아래와 같이 정렬된다.

arr[1] : [2, 4]
arr[2] : [1, 3, 4]
arr[3] : [2, 4]
arr[4] : [1, 2, 3]
arr[5] : []

 

시작점 1 방문 -> 방문순서[1] : 1 -> 큐에 삽입(Queue : {1})

정점 1과 연결된 {2,4} 중 방문하지 않은 정점 순서대로 탐색 (Queue : {})

 => 2 정점 방문 -> 방문순서[2] : 2 -> 큐에 삽입(Queue : {2})

 => 4 정점 방문 -> 방문순서[4] : 3 -> 큐에 삽입(Queue : {2,4})

정점 2와 연결된 {1,3,4} 중 방문하지 않은 정점 순서대로 탐색(Queue : {4})

 => 3 정점 방문 -> 방문순서[3] : 4 -> 큐에 삽입(Queue : {4,3})

정점 4와 연결된 {1,2,3} 중 방문하지 않은 정점 순서대로 탐색(Queue : {3})

 => 방문안한 정점 없음

정점 3과 연결된 {2,4} 중 방문하지 않은 정점 순서대로 탐색(Queue : {})

 => 방문안한 정점 없음

큐가 비었으므로 BFS 종료

따라서 방문순서[1] : 1, 방문순서[2] : 2, 방문순서[3] : 4, 방문순서[4] : 3, 방문순서[5] : 0

 

public class boj_24444_BFS_ASC {
	
	static ArrayList<Integer>[] arr;
	static int[] answer;
	static int n, cnt = 1;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		
		arr = new ArrayList[n+1];
		answer = new int[n+1];
		//그래프초기화
		for(int i = 0; i<=n; i++) {
			arr[i] = new ArrayList<>();
		}
		
		//list에 저장
		for(int j = 0; j < m; j++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a].add(b);
			arr[b].add(a);
		}
		
		//오름차순 정렬
		for(int k = 1; k <= n; k++) {
			Collections.sort(arr[k]);
		}
		
		bfs(r);
		
		for(int l = 1; l <= n; l++) {
			System.out.println(answer[l]);
		}
	}
	
	public static void bfs(int start) {
		Queue<Integer> queue = new LinkedList<>();
		boolean[] visited = new boolean[n+1];
		visited[start] = true;
		answer[start] = cnt;
		queue.add(start);
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			for(int x : arr[now]) {
				if(visited[x] == false) {
					visited[x] = true;
					cnt++;
					answer[x] = cnt;
					queue.offer(x);
				}
			}
		}
	}
}

 

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

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

 

24444와 동일한 유형으로 요구사항이 내림차순이다.

Collections.sort(배열, Collections.revreseOrder()) 로 내림차순을 구현하여 아래와 같이 정렬된다.

arr[1] : [4, 2]
arr[2] : [4, 3, 1]
arr[3] : [4, 2]
arr[4] : [3, 2, 1]
arr[5] : []

 

시작점 1 방문 -> 방문순서[1] : 1 -> 큐에 삽입(Queue : {1})

정점 1과 연결된 {4,2} 중 방문하지 않은 정점 순서대로 탐색 (Queue : {})

 => 4 정점 방문 -> 방문순서[4] : 2 -> 큐에 삽입(Queue : {4})

 => 2 정점 방문 -> 방문순서[2] : 3 -> 큐에 삽입(Queue : {4,2})

정점 4와 연결된 {3,2,1} 중 방문하지 않은 정점 순서대로 탐색(Queue : {2})

 => 3 정점 방문 -> 방문순서[3] : 4 -> 큐에 삽입(Queue : {2,3})

정점 2와 연결된 {4,3,1} 중 방문하지 않은 정점 순서대로 탐색(Queue : {3})

 => 방문안한 정점 없음

정점 3과 연결된 {4,2} 중 방문하지 않은 정점 순서대로 탐색(Queue : {})

 => 방문안한 정점 없음

큐가 비었으므로 BFS 종료

따라서 방문순서[1] : 1, 방문순서[2] : 3, 방문순서[3] : 4, 방문순서[4] : 2, 방문순서[5] : 0

 

public class boj_24445_BFS_DESC {
	
	static ArrayList<Integer>[] arr;
	static int[] answer;
	static int n, cnt = 1;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		
		arr = new ArrayList[n+1];
		answer = new int[n+1];
		//그래프초기화
		for(int i = 0; i<=n; i++) {
			arr[i] = new ArrayList<>();
		}
		
		//list에 저장
		for(int j = 0; j < m; j++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a].add(b);
			arr[b].add(a);
		}
		
		//내림차순 정렬
		for(int k = 1; k <= n; k++) {
			Collections.sort(arr[k], Collections.reverseOrder());
		}
		
		bfs(r);
		
		for(int l = 1; l <= n; l++) {
			System.out.println(answer[l]);
		}
	}
	
	public static void bfs(int start) {
		Queue<Integer> queue = new LinkedList<>();
		boolean[] visited = new boolean[n+1];
		visited[start] = true;
		answer[start] = cnt;
		queue.add(start);
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			for(int x : arr[now]) {
				if(visited[x] == false) {
					visited[x] = true;
					cnt++;
					answer[x] = cnt;
					queue.offer(x);
				}
			}
		}
	}
}