[JAVA] 백준 1085번 직사각형에서 탈출 : 단서로 풀기

1085번: 직사각형에서 탈출

 

1. 문제 추상화

 

왼쪽 아래 꼭지점이 (0.0)이고 오른쪽 위 꼭지점이 (w,h)인 직사각형 안에 (x,y)좌표의 A 지점이 있다. A에서 직사각형 경계까지의 최소거리를 구하라.

 

2. 알고리즘

 

조건을 토대로 단서를 구체적으로 파악해야한다. 단서를 확보하지 않고 비슷한 문제의 알고리즘을 떠올려 템플릿 쓰듯 사용하면 효율적인 코드를 작성하지 못한다. 단서를 토대로 필요한 알고리즘이 무엇인지 생각해야한다. 

 

첫 번째 방법 

 

직사각형을 네 부분으로 나눈 후, A점이 어느 영역에 속하는지 판단하는 방식으로 풀었다. 그러나 이 방식은 비효율적이다. A지점부터 최소거리가 가능한 값들을 구체적으로 파악하지 않고 범위를 나누어 푸는 알고리즘을 적용하였다. 범위를 사용하니 조건판단문이 많아져 효율적이 코드를 작성하지 못했다. 

 

두 번째 방법 

 

목적은 A 점과 직사각형 경계와의 최소 거리다. 

 

 

목적에 상응하는 경우의 수는 4가지이다. 입력된 값으로 4가지 값을 구할 수 있다. Math.min() 메소드를 이용하면 쉽게 최소 거리를 파악할 수 있다. 단서를 구체적으로 파악했다면 범위를 나눌 필요가 사라진다. 이처럼 알고리즘을 먼저 떠올리지 말고 단서 파악을 우선해야한다.

 

3. 코드

 

첫 번째 방법

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer stz = new StringTokenizer(br.readLine());
		
		int x = Integer.parseInt(stz.nextToken());
		int y = Integer.parseInt(stz.nextToken());
		int w = Integer.parseInt(stz.nextToken());
		int h = Integer.parseInt(stz.nextToken());
        
		 // 조건 판단 문이 많아지고 복잡해진다.
		if(x > w/2) {
			if(y > h/2) {
				bw.write(getMinDistance(w-x,h-y)+"");
			}else {
				bw.write(getMinDistance(w-x,y)+"");
			}
		}else {
			if(y > h/2) {
				bw.write(getMinDistance(x,h-y) +"");
			}else {
				bw.write(getMinDistance(x,y)+"");
			}
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
	
	public static int getMinDistance(int wide, int height) {
		return wide > height ? height : wide;
	}

}

 

 

두 번째 방법 

 

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

public class Main {

	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer stz = new StringTokenizer(br.readLine());
		
		int x = Integer.parseInt(stz.nextToken());
		int y = Integer.parseInt(stz.nextToken());
		int w = Integer.parseInt(stz.nextToken());
		int h = Integer.parseInt(stz.nextToken());
		
           	// 간단히 코드 3줄로 해결되었다.
		int xMin = Math.min(x, w-x);
		int yMin = Math.min(y, h-y);
		
		bw.write(Math.min(xMin, yMin)+"");
		
		bw.flush();
		bw.close();
		br.close();
	}

}