[백준] 29332번: 보물 지도 JAVA

 

근거를 통해 보물이 묻힌 위치를 유추할 수 있다.

문제

오른쪽으로 갈수록 x좌표가 증가하고 위쪽으로 갈수록 y좌표가 증가하는 무한한 좌표평면 위에 살고 있는 여러분은 어느 날 보물 지도를 주웠다. 아쉽게도 여러분이 주운 보물 지도는 여러 개의 조각으로 나뉘어 있어 정확히 어디에 보물이 묻혀 있는지는 알 수 없었다. 그래도 열심히 주어진 지도 조각들을 분석한 결과, 보물이 묻힌 위치에 대해 다음과 같은 정보를 얻을 수 있었다.

• 보물이 묻혀 있는 위치는 어느 정수 격자점 위이다.
• 보물이 묻혀 있는 위치를 나타내는 N개의 단서가 있다. 각 단서는 두 정수 x_i, y_i와 문자 d_i로 이루어져 있다. 문자 d_i는 L, R, U, D 중 하나이며, 각각 보물이 (x_i, y_i) 좌표보다 왼쪽, 오른쪽, 위쪽, 아래쪽에 묻혀 있음을 의미한다.
• 모든 정보는 서로 모순되지 않는다. 즉, 임의의 두 단서를 조합했을 때 가능한 보물의 위치가 존재하지 않는 경우는 없다.

여러분은 모은 단서를 토대로 보물이 있을 수 있는 모든 위치를 탐색해 보려고 한다. 여러분이 탐색해야 할 격자점의 수를 구해보자. 만약 주어진 단서가 불충분해서 탐색해야 할 위치가 무한히 많다면, 대신 Infinity를 출력한다.

 

입력

첫째 줄에 보물이 묻혀 있는 위치를 나타내는 단서의 수 N이 주어진다. (1≤N≤100,000) 

다음 N개의 줄에 x_i, y_i, d_i가 공백을 두고 주어진다. 이는 보물이 x_i, y_i 좌표의 d_i 방향에 묻혀 있다는 의미이다. (−10^9≤x,y≤10^9); d_i는 L, R, U, D 중 하나)

입력에서 주어지는 수는 모두 정수이다.

 

출력

보물이 묻혀 있을 수 있는 정수 격자점의 수를 출력한다. 만약 그러한 격자점이 무한히 많다면 대신 Infinity를 출력한다. 

 

접근

무한한 공간이므로 닫힌 공간을 만들어야 범위를 지정 할 수 있다.

왼쪽, 오른쪽, 위쪽, 아랫쪽 단서가 모두 있어야 닫힌 공간이 생성된다.

모든 단서에 대해 참이 되어야 함으로 결국 닫힌 공간은 하나만 존재한다.

 

따라서 각 방향에 대해 다음과 같은 조건을 저장한다

왼쪽 : 해당 점의 왼쪽 방향 (x 감소 방향)으로 유효함으로 x의 최소값을 지정한다.

오른쪽 : 해당 점의 오른쪽 방향 (x 증가 방향)으로 유효함으로 x의 최대값을 지정한다.

 

위쪽 : 해당 점의 위쪽 방향 (y 증가 방향)으로 유효함으로 x의 최대값을 지정한다.

아래쪽 : 해당 점의 아래쪽 방향 (y 감소 방향)으로 유효함으로 y의 최소값을 지정한다.

 

모든 구간을 탐색 한 후,

x의 최소, 최대 , y의 최소, 최대에 변함이 없다면 열린 공간임으로 격자점이 무한히 많아지기에 Infinity를 출력한다.

닫힌 공간이라면 닫힌 공간에 면적을 출력한다. 이 때 곱셈의 값이 Integer 최대값을 넘을 수 있음으로 (10억 * 10억)

long 형으로 보정한 뒤 계산한다.

(x 최대 - x 최소 - 1) * ( y 최대 - y 최소 -1 )

구현

package 백준;

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

//https://www.acmicpc.net/problem/29332
public class 보물지도 {
	
	static final int INF  = Integer.MAX_VALUE/2;
	static int L = INF; //왼쪽
	static int R = -INF; //오른쪽
	static int U = -INF; //위쪽
	static int D = INF; //아래쪽
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st;
		while(n-- >0) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()); 
			int y = Integer.parseInt(st.nextToken());
			char cmd = st.nextToken().charAt(0);
			switch (cmd) {
				case 'L': {
					L = Math.min(L,x); //왼쪽이면 x 최소값
					break;
				}
				case 'R': {
					R = Math.max(R,x); //오른쪽이면 x 최대값
					break;
				}
				case 'U': {
					U = Math.max(U,y); //위쪽이면 y 최대값
					break;
				}
				case 'D': {
					D = Math.min(D,y); //아래쪽이면 y 최대값
					break;
				}
			}
		}
		//하나라도 초기값인 경우, 무한
		if(L == INF || R == -INF || U == -INF || D == INF) {
			System.out.println("Infinity");
		}else {
			//곱셈을 통해 21억이 넘을 수 있음으로 long 형으로 변환후 곱셈
			long w = L - R -1;
			long h = D - U - 1;
			System.out.println(w*h);
		}
		br.close();
	}
}