[SWEA-8382] 방향전환

이 문제는 SW 아카데미 D4 레벨 문제이다.

싸피 수업을 들으며 CT시간에 접한 문제인데, 간단해 보였는데 생각보다 어려웠다.

 

처음에는 BFS를 이용해서 접근했는데, 이렇게 풀면 바로 시간초과가 난다고 해서 다른 방법을 고민하던 중 선생님께서 다른 방법을 알려주셨다. 

 

사실 이렇게 간단한 걸 보고 좀.. 당황했다.

 

풀이를 해 보자면, 

sC와 sR 은 각각 시작 좌표, fC와 fR은 도착 좌표이다.

x와 y는 도착점에서 시작점을 빼 준 값을 절댓값으로 처리해 준 것인데, (0,0) 부터 (x,y)까지 가는 것으로 계산하기 위해서이다.

 

여기서 t는 x좌표와 y좌표에서 가장 가까운 y=x 상의 좌표를 의미한다.

이 점을 구하는 이유는, (t,t)에서는 가로로 먼저 출발하든, 세로로 먼저 출발하든 값이 같기 때문이다.

따라서 (t,t)부터 (x,y)까지의 최솟값을 구하는 것이 쉬워진다. 이 전에 방법이 가로였는지 세로였는지 신경 쓸 필요 없이 당장 유리한 방법을 택할 수 있기 때문이다. 

 

y = x 직선을 그렸을 때, (1,1), (2,2) 등의 각 점으로 가기 위해서는 두 점의 합 만큼의 거리가 필요하다. 

그래서 답에 2*t 만큼을 더해주고 (t,t)점에서 (x,y)점까지의 최소 거리를 구해주기 위해 (x-t)와 (y-t)의 절댓값을 더해주면 값을 구할 수 있다.

import java.util.Scanner;

public class 방향전환 { //SWEA
	static int sR, sC, fR, fC, ans;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for(int tc=1; tc<= T; tc++) {
			sC = sc.nextInt(); //시작 y좌표
			sR = sc.nextInt(); //시작 x좌표
			fC = sc.nextInt(); //도착 y좌표
			fR = sc.nextInt(); //도착 x좌표
			
			int x = Math.abs(fC - sC);
			int y =  Math.abs(fR - sR);
			
			int t = (x+y)/2;
			ans = 2*t + Math.abs(x-t) + Math.abs(y-t);
			System.out.println("#"+tc+" "+ans);
		}
	}
}