[SWEA] 3349. 최솟값으로 이동하기

• 메모리 : 21,708 KB
• 실행시간 : 126 ms
• 코드길이 : 1,503 B
• 소요시간 : 1H 40M
• BFS로 풀려고 하다가 x좌표가 더 작은 경우로 이동하지 않는다 하더라도 시간 초과가 날 것 같아서 생각해보고 교수님 코드를 참고해보니 그냥 수학적으로 계산하는 방법이 있었다… 나중에 꼭 재풀이가 필요할 것 같다.

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

public class Solution_D4_3349_최솟값으로이동하기 {

	static int W, H, N, ans;
	static Point[] points;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder answer = new StringBuilder();

		int T = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= T; tc++) {
			ans = 0;
			st = new StringTokenizer(in.readLine(), " ");
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			points = new Point[N];

			for (int n = 0; n < N; n++) {
				st = new StringTokenizer(in.readLine(), " ");
				points[n] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			}

			for (int n = 1; n < N; n++) {
				int x = points[n].x - points[n - 1].x;
				int y = points[n].y - points[n - 1].y;

				if (x * y > 0) {
					ans += Math.min(Math.abs(x), Math.abs(y));
					ans += Math.abs(Math.abs(x) - Math.abs(y));
				} else if (x * y == 0) {
					ans += Math.abs(x + y);
				} else {
					ans += Math.abs(x) + Math.abs(y);
				}
			}

			answer.append('#').append(tc).append(' ').append(ans).append('\n');
		}

		System.out.println(answer);
	}

	private static class Point {
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}

	}
}