[Baekjoon] 5006_Horror List

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

---

< Horror List >

 

문제 풀이 

 

bfs를 활용하여 horror 영화와, 유사한 영화를 찾는다.

 

my solution (Java)

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

public class _5006_ { // Horror List
	static ArrayList<ArrayList<Integer>> list;
	static int visited[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int h = Integer.parseInt(st.nextToken());
		int l = Integer.parseInt(st.nextToken());

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

		Queue<Integer> queue = new LinkedList<>();
		visited = new int[n];

		for (int i = 0; i < n; i++) {
			visited[i] = Integer.MAX_VALUE;
		}

		for (int i = 0; i < h; i++) {
			int num = Integer.parseInt(st.nextToken());
			queue.add(num);
			visited[num] = 0;
		}

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

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

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

		bfs(queue);

		int value = 0, result = 0;

		for (int i = 0; i < n; i++) {
			if (value < visited[i]) {
				value = visited[i];
				result = i;
			}
		}
		System.out.println(result);
	}

	private static void bfs(Queue<Integer> queue) {
		while (!queue.isEmpty()) {
			int num = queue.poll();
			for (int i = 0; i < list.get(num).size(); i++) {
				if (visited[list.get(num).get(i)] == Integer.MAX_VALUE) {
					visited[list.get(num).get(i)] = visited[num] + 1;
					queue.add(list.get(num).get(i));
				}
			}
		}
	}
}

변수)
n, h, l : 영화의 개수, horror list에 포함된 영화의 수, 유사성의 데이터 수
visited : Horror Index
list : 유사한 영화 정보
value, result : Horror Index가 가장 높은 값, Horror Index가 가장 높은 영화

 

Main

영화의 개수, horror list에 포함된 영화의 수, 유사성의 데이터 수를 입력받는다. 영화의 개수만큼 Horror Index를 저장하는 배열을 만들어 Integer.MAX_VALUE로 초기화한다. horror list에 포함된 영화의 수만큼 영화 ID를 입력받아 queue에 저장하고, Horror Index를 0으로 저장한다. 유사성의 데이터 수만큼 데이터를 입력받아 ArrayList에 양방향으로 저장한다. bfs를 호출한다.

 

최종 visited를 탐색하며 horror Index가 높은 값 중 ID가 낮은 값을 출력한다.

 

bfs

Queue가 빌 때까지 다음 과정을 반복한다.

1) queue poll

2) 아직 방문하지 않은 곳이라면 visited 값을 연결된 영화의 horror index+1로 업데이트한 후 queue에 추가한다.

 

---

---