[백준] 17197. Fence Planning (Java)

 

문제

17197번: Fence Planning

 

 

알고리즘

그래프, 너비우선탐색(BFS)

 

풀이

그룹을 판별하지 않은 각 소를 시작으로 그래프를 탐색해

묶인 소들의 miny, minx, maxy, maxx 좌표를 찾는다.

 

울타리는 위 네가지 좌표가 포함된 직사각형이므로

울타리의 둘레는 (maxy-miny) * 2 + (maxx-minx) * 2) 가 되고, 이에 대한 최소값을 갱신시킨다.

 

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] pos = new int[N + 1][2];
		boolean[] visited = new boolean[N + 1];

		List<Integer>[] graph = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++)
			graph[i] = new ArrayList<>();

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			pos[i][0] = Integer.parseInt(st.nextToken());
			pos[i][1] = Integer.parseInt(st.nextToken());
		}

		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[a].add(b);
			graph[b].add(a);
		}
        
		long min = Long.MAX_VALUE;

		Queue<Integer> queue = new LinkedList<>();
		for (int i = 1; i <= N; i++) {
			if (visited[i]) continue;
			visited[i] = true;
			queue.add(i);

			int miny = pos[i][0];
			int maxy = pos[i][0];				
			int minx = pos[i][1];				
			int maxx = pos[i][1];				

			while (!queue.isEmpty()) {
				int cur = queue.poll();

				for (int next : graph[cur]) {
					if (visited[next]) continue;

					miny = Math.min(miny, pos[next][0]);
					maxy = Math.max(maxy, pos[next][0]);					
					minx = Math.min(minx, pos[next][1]);
					maxx = Math.max(maxx, pos[next][1]);

					visited[next] = true;
					queue.add(next);
				}
			}
			
			min = Math.min(min, (maxy-miny) * 2 + (maxx-minx) * 2);
		}
		
		System.out.println(min);
	}
}