개미

문제

백준 10158번 - 개미

언어

Java

순서도

x 축 이동 거리에서 반복 이동 제거
y 축 이동 거리에서 반복 이동 제거
구한 이동 거리를 이용해서 이동 후의 x 좌표와 y 좌표 구하기

문제 풀이 step 1

가로 길이 w, 세로 길이 h 인 2차원 격자가 주어집니다.
왼쪽 아래는 (0, 0) 이고, 오른쪽 위는 (w, h) 이며, 개미의 시작 위치 (p, q) 입니다.
처음에는 오른쪽 위 45 도로 이동합니다. 1 시간 후에는 (p + 1, q + 1) 로 옮겨 갑니다.
속도를 계속해서 유지하며, 경계면에 부딪치면 같은 속력으로 반사되어 움직입니다.
주어진 t 시간 후에 격자 안에서 개미의 좌표를 구하는 문제입니다.

문제 풀이 step 2

본 문제는 x 축과 y 축을 별개로 나눠서 생각해서 풀 수 있습니다.
- 왜냐하면, x 축 이동과 y 축 이동이 서로에게 영향을 주지 않고, 이동하기 때문입니다.
따라서 x 축 이동은 총 (2 x w) 만큼 반복하면서 이동할 것입니다.
- w 는 가로 길이를 의미합니다.
- 2 x w = (오른쪽으로 이동하는 w) + (왼쪽으로 이동하는 w)
그리고 y 축 이동은 총 (2 x h) 만큼 반복하면서 이동할 것입니다.
- h 는 세로 길이를 의미합니다.
- 2 x h = (아래로 이동하는 h) + (위로 이동하는 h)
우선, 현재 위치에서 x 좌표와 y 좌표에 각각 t 를 더합니다.
그리고 반복 이동을 제거합니다. 이는 x 좌표와 y 좌료를 각각 (2 x w) 와 (2 x h) 로 나머지 연산을 해주면 됩니다.
그리고 x 좌표가 w 보다 크다면, w 를 초과한 만큼 왼쪽으로 이동하면 되고, y 좌표도 마찬가지로 h 보다 크다면, h 를 초과한 만큼 위로 이동하면 됩니다.
위 과정을 통해서 구한 x 좌표와 y 좌표를 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

후기

시뮬레이션 방식으로 풀어봤으나 역시나 시간 초과가 발생했습니다.
Node.js 로 풀었는데, 시간 초과가 나서 Java 로 풀었습니다.
Java 11 로 풀었는데, 시간 초과가 나서 Java 8 로 풀었습니다.
x 축과 y 축을 나눠서, 각각의 이동을 고려하는 것이 상당히 신선하고 재미있었습니다.
푸는 과정에서 상당히 재미를 느꼈지만, 언어별로 풀리지 않는 상황이 발생해서 시행 착오를 많이 겪었습니다.
가장 중요한 포인트는 x 축과 y 축이 서로 영향을 주지 않으니, x 축과 y 축을 별개로 나눠서 생각할 수 있다는 것!!

소스 코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		// 최대한 시간을 줄이기 위해서 BufferedReader 와 BufferedWriter 사용
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String [] str = br.readLine().split(" ");
		int w = Integer.parseInt(str[0]);
		int h = Integer.parseInt(str[1]);

		str = br.readLine().split(" ");
		int p = Integer.parseInt(str[0]);
		int q = Integer.parseInt(str[1]);

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

		// 반복 이동 제거
		int x = (p + t) % (2 * w);
		int y = (q + t) % (2 * h);

		// w 를 초과한 만큼 좌로 이동
		// h 를 초과한 만큼 위로 이동
		if(x > w) x = w - (x - w);
		if(y > h) y = h - (y - h);

		// 출력
		bw.write(x + " " + y);
		bw.flush();
	}
}