[백준: Java] 32620 - 점령

[문제]

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

그래프를 탐색하는 데 있어서, 이웃 노드를 하나 이상 점령한다는 점에서 BFS 탐색을 떠올렸습니다.

 

또한 i번 노드로 이동하는 데 있어, 현재 기력이 요구하는 기력 이상이라면 이동할 수 있다는 점에서 그리디 접근 법을 떠올렸습니다.

 

즉 이동하고자 하는 노드와 인접한 노드를 방문한 상태이고, 요구하는 기력이 현재 기력 이하라면 모든 노드를 탐색할 수 있다는 점에서 최대한 많은 노드를 탐색해야 얻을 수 있는 기력을 최대로 만들 수 있습니다.

 

그렇기 때문에 BFS 탐색에 사용하는 자료구조로 일반적인 큐를 사용하지 않고 우선순위 큐를 사용해, 인접하면서 요구하는 기력이 작은 순으로 탐색하는 것입니다.

 

요약하자면

1. 다음 노드를 방문하기 위해서는 인접하는 노드를 하나 이상 방문할 것
2. 다음 노드가 요구하는 기력이 현재 기력 이하일 것
3. 위 두 조건을 모두 만족한다면 다음 노드로 이동 가능

---

[초기화]

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n, m, r;
	static int[] a;
	static int[] b;
	static int u, v;
	static ArrayList<Node>[] graph;
	
	static class Node {
		int num, require, acquire;

		public Node(int num, int require, int acquire) {
			super();
			this.num = num;
			this.require = require;
			this.acquire = acquire;
		}
	}
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		
		a = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i <= n; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		
		b = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i <= n ; i++) {
			b[i] = Integer.parseInt(st.nextToken());
		}
		
		graph = new ArrayList[n + 1];
		for(int i = 1; i <= n; i++) {
			graph[i] = (new ArrayList<Node>());
		}
		
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken());
			v = Integer.parseInt(st.nextToken());
			graph[u].add(new Node(v, a[v], b[v]));
			graph[v].add(new Node(u, a[u], b[u]));
		}
		
		
		solve();
	}

코드 작성시, 편의를 위해 노드 클래스를 정의하였습니다.

---

[풀이]

	static void solve() {
		long current_energy = 0;  // 각 노드에서 얻을 수 있는 최대 기력은 10억 -> 3번만 누적되면 int 범위 초과
		boolean[] visited = new boolean[n + 1];
		PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.require - o2.require);  // 필요한 기력이 작은 순으로
		pq.add(new Node(r, a[r], b[r]));
		
		while(!pq.isEmpty()) {
			Node current = pq.poll();

			if(!visited[current.num] && current_energy >= current.require) {  // 아직 정복되지 않았고, 취할 수 있는 노드라면 -> 해당 조건 때문에 초기화시 r을 방문처리 하지 않음
				visited[current.num] = true;  // 정복
				current_energy += current.acquire;  // 기력 취함
				
				for(Node next: graph[current.num]) {  // 정복한 노드와 인접한 노드를 탐색 범위에 추가
					pq.add(next);
				}
			}
		}
		
		System.out.println(current_energy);
	}

구성은 기본적인 BFS와 동일하나 주의할 것이 있습니다.

1. 현재 기력은 각 노드당 최대 10억이므로 더하다 보면 int 범위를 초과할 수 있기 때문에 long 타입으로 지정해야 함
2. 습관적으로 시작 노드를 방문처리 하는 것을 주의해야 함
   • 보통의 BFS는 다음으로 이동하고자 하는 곳이 방문했는지 체크하지만, 해당 문제의 경우 현재 노드를 방문했는지 체크하는 것이므로, 초기에 방문처리를 했다면 while 문은 아무것도 수행하지 않고 종료됨

---

[전체 코드]

package 백준.골드;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ_32620_점령 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n, m, r;
	static int[] a;
	static int[] b;
	static int u, v;
	static ArrayList<Node>[] graph;
	
	static class Node {
		int num, require, acquire;

		public Node(int num, int require, int acquire) {
			super();
			this.num = num;
			this.require = require;
			this.acquire = acquire;
		}
	}
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		
		a = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i <= n; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		
		b = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i <= n ; i++) {
			b[i] = Integer.parseInt(st.nextToken());
		}
		
		graph = new ArrayList[n + 1];
		for(int i = 1; i <= n; i++) {
			graph[i] = (new ArrayList<Node>());
		}
		
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken());
			v = Integer.parseInt(st.nextToken());
			graph[u].add(new Node(v, a[v], b[v]));
			graph[v].add(new Node(u, a[u], b[u]));
		}
		
		
		solve();
	}
	
	static void solve() {
		long current_energy = 0;  // 각 노드에서 얻을 수 있는 최대 기력은 10억 -> 3번만 누적되면 int 범위 초과
		boolean[] visited = new boolean[n + 1];
		PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.require - o2.require);  // 필요한 기력이 작은 순으로
		pq.add(new Node(r, a[r], b[r]));
		
		while(!pq.isEmpty()) {
			Node current = pq.poll();
			
			if(!visited[current.num] && current_energy >= current.require) {  // 아직 정복되지 않았고, 취할 수 있는 노드라면 -> 해당 조건 때문에 초기화시 r을 방문처리 하지 않음
				visited[current.num] = true;  // 정복
				current_energy += current.acquire;  // 기력 취함
				
				for(Node next: graph[current.num]) {  // 정복한 노드와 인접한 노드를 탐색 범위에 추가
					pq.add(next);
				}
			}
		}
		
		System.out.println(current_energy);
	}
 }

---