(백준) 프린트전달 _ 23887

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

 

🐢 설명

BFS + 트리DP 문제이다.

 

먼저 2차원 배열에 위치하는 학생들이 존재하고, 이들은 8방향으로 주위 학생들에게 자신의 유인물 한개를 제외하고 넘겨주게 된다. 이때 모두가 유인물을 받기 위해서 학생들이 몇개의 유인물을 받아야하는지 출력하면 된다. 만약 모두에게 유인물을 넘겨줄 수 없다면, 즉 8방향을 탐색해도 넘겨줄 수 없는 자리배치로 있다면 -1을 출력하면 된다.

 

최초에 유인물을 받는 학생이 곧 root 노드가 되고 이 학생부터 bfs를 돌면서 트리구조를 만들어주면 된다. 이때 주의할 점이 동시에 유인물을 나눠받는 학생은 번호가 낮은 학생으로부터 유인물을 받게 된다는 점이다. 따라서 Queue로 bfs를 돌 때 노드 하나당 인접한 노드의 개수만큼만 for문을 돌고, 인접한 노드들은 번호순서대로 정렬해서 다음 큐에 차곡차곡 넣어줘야 한다.

 

예시를 통해 말하자면 3번 학생을 넣고, 8방향 탐색을 통해 9, 6, 4, 7번 학생을 인접 노드로 찾게 되었다. 이때 번호 순서를 우선하여 넣어줘야 하므로 4 -> 6 -> 7 -> 9 번 순으로 다음 bfs를 진행해줘야 한다. 또한 한쪽 노드에서 끝까지 진행하지 못하게 하나의 노드에서 담은 인접 노드의 개수만큼만 for문을 돌리게 해주는 것이다.

 

그럼 3  |  4, 6, 7, 9  |  5, 2  |  1  |  8 이렇게 순서대로 유인물을 넘겨주고 트리도 조건에 맞게 생성된다.

 

그리고 인접 노드를 번호순으로 넣기위해 PriorityQueue로 담고나서 전체 Queue에 담을 때 주의할 사항이 있는데 addAll()로 넣어주면 안된다. 우선순위 큐는 Heap 자료구조이므로 현재 순서가 정렬된 순서가 아니다. 따라서 poll()로 하나씩 뽑아서 넣어줘야 의도한대로 번호가 낮은 순서대로 넣어줄 수 있다.

 

이후 탐색한 노드의 개수가 K학생수 - 1개가 맞다면(루트 학생 제외한 수) root학생을 기준으로 트리를 돌면서 전달받은 유인물의 개수를 dp배열에 담아주면 된다.
dp식 : dp[현재노드] = 1 + dp[자식노드들]  : (자기가 받아야 될 유인물 한개 + 자식들이 받은 유인물의 총 합)

🐢코드

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

public class Main {
	static int N;
	static int M;
	static int K;
	static ArrayList<Integer>[] adj;
	static int[][] map;
	static int[] dp;
	static int R;
	static boolean[] visited;
	static int childCount = 0;
	static StringBuilder answer = new StringBuilder();
	static HashMap<Integer, Dot> hashMap = new HashMap<>();

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

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		map = new int[N + 1][M + 1];
		adj = new ArrayList[K + 1];
		for (int i = 0; i < K + 1; i++) {
			adj[i] = new ArrayList<>();
		}
		visited = new boolean[N * M + 1];
		dp = new int[K + 1];

		for (int i = 1; i <= K; i++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			map[y][x] = i;
			hashMap.put(i, new Dot(i, y, x));
		}
		R = Integer.parseInt(br.readLine());

		makeTree(hashMap.get(R).number);

		if (childCount == K - 1) {
			dfs(R);
			for (int i = 1; i < K + 1; i++) answer.append(dp[i]).append(" ");
		} else {
			answer.append("-1");
		}

		System.out.print(answer);
	}

	private static void dfs(int root) {
		dp[root] = 1;

		for (int child : adj[root]) {
			dfs(child);
			dp[root] += dp[child];
		}
	}

	private static void makeTree(int number) {
		int[] dy = {-1, 1, 0, 0, 1, 1, -1, -1};
		int[] dx = {0, 0, 1, -1, -1, 1, -1, 1};

		Queue<Integer> queue = new LinkedList<>();
		queue.add(number);
		visited[number] = true;

		while (!queue.isEmpty()) {
			int SIZE = queue.size();
			PriorityQueue<Integer> childPq = new PriorityQueue<>();

			for (int i = 0; i < SIZE; i++) {
				Dot cur = hashMap.get(queue.poll());
				int cy = cur.y;
				int cx = cur.x;
				int cn = cur.number;

				for (int d = 0; d < 8; d++) {
					int ny = cy + dy[d];
					int nx = cx + dx[d];

					if (ny <= 0 || nx <= 0 || ny > N || nx > M) continue;
					if (visited[map[ny][nx]]) continue;
					if (map[ny][nx] > 0) {
						visited[map[ny][nx]] = true;
						childCount++;
						adj[cn].add(map[ny][nx]);
						childPq.add(map[ny][nx]);
					}
				}
			}
			if (!childPq.isEmpty()) {
				while (!childPq.isEmpty()) {
					queue.add(childPq.poll());
				}
			}
		}
	}

	private static class Dot {
		int number;
		int y;
		int x;

		public Dot(int number, int y, int x) {
			this.number = number;
			this.y = y;
			this.x = x;
		}
	}
}

🐢 마무리