[백준/자바] 10158 개미

[백준/자바] 10158

 

📌 문제 

가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오른쪽 위 45도 방향으로 일정한 속력으로 움직이기 시작한다. 처음에 (p,q)에서 출발한 개미는 1시간 후에는 (p+1,q+1)로 옮겨간다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다.

위 그림은 6×4 격자에서 처음에 (4,1)에서 출발한 개미가 움직인 길을 보여주고 있다. 처음에 (4,1)에 있는 개미는 2시간 후에 (6,3)에 있으며 8시간 후에 (0,1)에 있다. 만일 그 개미가 처음에 (5,3)에 있었다면 매 시간마다 (6,4), (5,3), (4,2), (3,1)로 움직인다. 
여러분은 크기 w×h인 격자 공간에서 처음에 (p,q)에서 출발하는 개미의 t시간 후의 위치 (x,y)를 계산하여 출력해야 한다. 개미는 절대 지치지 않고 같은 속력으로 이동한다고 가정한다. 
문제에서 w와 h는 자연수이며 범위는 2 ≤ w,h ≤ 40,000이다. 그리고 개미의 초기 위치 p와 q도 자연수이며 범위는 각각 0 < p < w과 0 < q < h이다. 그리고 계산할 시간 t의 범위는 1 ≤ t ≤ 200,000,000이다. 

 

 

⚔ 입력

첫줄에는 w와 h가 공백을 사이에 두고 주어진다. 그 다음 줄에는 초기 위치의 좌표값 p와 q가 공백을 사이에 두고 주어진다. 3번째 줄에는 개미가 움직일 시간 t가 주어진다. 

 

 

📣 출력

출력은 t 시간 후에 개미의 위치 좌표 (x,y)의 값 x와 y를 공백을 사이에 두고 출력한다. 

 

 

 

 

---

 

 

 

 

 

💡 코드 구현

 

시뮬레이션 방식으로 시간초과가 나는 코드이다. 

 

나름 사이클을 탐지해서 반복문을 줄여준다고 해봤지만 여전히 시간초과가 났다. 

 

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

public class Main {
	private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {

		// 격자 공간의 크기 입력
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		int w = Integer.parseInt(st.nextToken());
		int h = Integer.parseInt(st.nextToken());

		// 초기 위치 입력
		st = new StringTokenizer(bufferedReader.readLine());
		int p = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());

		int initialP = p;
		int initialQ = q;

		int time = Integer.parseInt(bufferedReader.readLine());

		boolean rightUp = true;
		boolean rightDown = false;
		boolean leftUp = false;
		boolean leftDown = false;

		int count = 0;
		for (int i = 0; i < time; i++) {
			count++;
			if (rightUp) {
				p += 1;
				q += 1;
				if (p == w && q == h) {
					rightUp = false;
					leftDown = true;
				} else if (p == w) {
					rightUp = false;
					leftUp = true;
				} else if (q == h) {
					rightUp = false;
					rightDown = true;
				}
			} else if (rightDown) {
				p += 1;
				q -= 1;
				if (p == w && h == 0) {
					rightDown = false;
					leftUp = true;
				} else if (q == 0) {
					rightDown = false;
					rightUp = true;
				} else if (p == w) {
					rightDown = false;
					leftDown = true;
				}

			} else if (leftUp) {
				p -= 1;
				q += 1;
				if (p == 0 && q == h) {
					leftUp = false;
					rightDown = true;
				} else if (q == h) {
					leftUp = false;
					leftDown = true;
				} else if (p == 0) {
					leftUp = false;
					rightUp = true;
				}
			} else if (leftDown) {
				p -= 1;
				q -= 1;
				if (p == 0 && q == 0) {
					leftDown = false;
					rightUp = true;
				} else if (p == 0) {
					leftDown = false;
					rightDown = true;
				} else if (q == 0) {
					leftDown = false;
					leftUp = true;
				}
			}

			if (p == initialP && q == initialQ && rightUp) {
				time = (time % count) + 1;
				i = 0;
			}
		}

		System.out.printf("%d %d%n", p, q);
	}
}

 

 

사이클은 개미가 다시 원위치로 돌아온 시점이 될 것이므로 아래와 같이 count 변수를 통해 구할 수 있었다. 

 

	if (p == initialP && q == initialQ && rightUp) {
				time = (time % count) + 1;
				i = 0;
			}

 

 

 

하지만 이렇게 풀면 정답을 통과할 수 없다. 왜 그런고 하면 최악의 경우 사이클을 찾는데까지 모든 판을 다 거쳐야 하고 

이 최대 40000 * 40000의 시간 복잡도를 의미하기 때문이다. 

 

따라서 이 문제를 풀려면 수학적인 법칙을 찾아야 하는데, x좌표와 y좌표를 따로 놓고 보면 보이기 시작한다. 

 

(4,1)

(5,2)

(6,3)

(5,4)

(4,3)

(3,2)

(2,1)

(1,0)

(0,1) 

 

즉, w, h 내에서 x, y는 오르고 내리고를 반복한다. 

 

x: 4 -> 5 -> 6 (w) -> 5 -> 4 -> 3 -> 2-> 1 -> 0 (0지점) -> 1 -> 2 -> 3 -> ...

y: 1 -> 2 -> 3 -> 4 (h) -> 3 -> 2 -> 1 -> 0 (0지점) -> 1 -> ... 

 

이를 좌표평면에 나타내면 다음과 같다. 

 

 

사이클이 w * 2 인 함수이므로 초기 시작 지점 p 와 시간 t 를 더한 값에 w * 2를 모듈러 연산을 하면 

 

(4 + 0) % 12 => 4 

(4 + 1) % 12 => 5

(4 + 2) % 12 => 6

(4+ 3) % 12 => 5 

.

.

.

따라서 

수식으로 표현하면 

 

x = (p+t) % 2w 

y = (q+t) % 2h 

 

 

그런데 문제는 x 좌표의 경우 감소시에 7 ~ 12 값이 나오게 되고 y 좌표의 경우도 감소시에 5 ~ 8 값이 나오게 된다. 

 

수식적으로 감소하는 부분은

p + t > w

q + t > h 

이다. 

 

따라서 해당 부분에 대해서는 w에서 해당 부분 만큼을 차감해준 값이 될 것이다. 

=> w - (x - w) = 2w - x

 

이렇게 함으로써 시간 복잡도를 O(1)까지 줄일 수 있게 되고 정해진 시간내에 통과한다. 

 

 

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

public class Main {
   private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

   public static void main(String[] args) throws IOException {

      StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
      int w = Integer.parseInt(st.nextToken());
      int h = Integer.parseInt(st.nextToken());

      st = new StringTokenizer(bufferedReader.readLine());
      int p = Integer.parseInt(st.nextToken());
      int q = Integer.parseInt(st.nextToken());

      int t = Integer.parseInt(bufferedReader.readLine());

      int x = (p + t) % (w * 2);
      int y = (q + t) % (h * 2);

      if (x > w) {
         x = 2 * w - x;
      }

      if (y > h) {
         y = 2 * h - y;
      }

      System.out.printf("%d %d", x, y);
   }
}

 

 

 

---