[백준] 10158번 개미
https://www.acmicpc.net/problem/2164
문제
가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오른쪽 위 45도 방향으로 일정한 속력으로 움직이기 시작한다. 처음에 (p,q)에서 출발한 개미는 1시간 후에는 (p+1,q+1)로 옮겨간다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다.
예를 들어 6×4 격자에서 처음에 (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를 공백을 사이에 두고 출력한다.
나의 답안
1번째 시도 (실패)
개미가 (p, q) 좌표에서 시작, 초기엔 시간마다 (+1, +1) 씩 이동하다가
x한계선에 부딪히면 (-1, +1)이동,
y한계선에 부딪히면 (+1, -1) 이동,
x, y 한계선에 부딪히면 (-1, -1) 이동하도록 설계했다.
이동할 때마다 이동할 위치를 미리 확인하여 한계선 여부를 확인하고,
확인된 한계선의 좌표 이동값만 -1을 곱하여 바꿔주도록 했다.
<1차 시도(실패 코드)>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 상하좌우 확인용 배열
// int[] dr = { -1, 1, 0, 0 };
// int[] dc = { 0, 0, -1, 1 };
// 시간당 이동량
int[] move = { 1, 1 };
// 개미 현재위치 변수
int r, c;
// 개미가 이동할 위치 변수
int nr, nc;
// 좌표상으로 개미의 이동 가능 범위가 x : 0 ~ w, y : 0 ~ h 이므로
// => 배열로는 w+1행 h+1열 지도 생성해야 함
int w = Integer.parseInt(st.nextToken());
int h = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
// 개미 위치 입력받음
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
// 시간 입력
int time = Integer.parseInt(br.readLine());
for (int t = 1; t <= time; t++) {
// 사방 탐색
nr = r + move[0];
nc = c + move[1];
// nr값이 범위를 넘으면 => 이동량 (-1, 1)
if (nr < 0 || nr > w) move[0] *= -1;
// nc값이 범위를 넘으면 => 이동량 (1, -1)
if (nc < 0 || nc > h) move[1] *= -1;
// 개미 이동
r += move[0];
c += move[1];
}
// time시간 후 개미 위치 출력
System.out.println(r + " " + c);
}
}
2번째 시도 (성공)
1차 시도에서 시간 초과 발생. time이 최대 2억이므로 for문을 사용하면 안될 것이라고 판단했다.
- time을 최대 좌표값으로 나눴을 때
몫이 짝수이면 => 2바퀴 돌고 제자리로 돌아오고, 이동량은 그대로 +1
몫이 홀수이면 => 1바퀴 돌아 원래 자리의 대칭점으로 이동. 이동량은 반대인 -1 - time을 좌표값으로 나눈 나머지만큼 이동해주면 최종 위치값이 된다.
<2차 코드(성공)>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class S3_10158_개미 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 개미 현재위치 변수
int r, c;
st = new StringTokenizer(br.readLine());
// 개미 위치 입력받음
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
// 시간 입력
int time = Integer.parseInt(br.readLine());
// 몫이 짝수이면 다시 제자리로 돌아온 것과 같음
if (time / w % 2 == 0) {
// 제자리에서 (+1 * 나머지) 만큼 이동
r = r + (time % w) > w ? w - (r + (time % w) - w) : r + (time % w);
// 몫이 홀수이면 원래 자리의 대칭점으로 이동한 것과 같음
} else {
// 대칭점에서 (-1 * 나머지) 만큼 이동
r = r + (time % w - w) < 0 ? - (r + (time % w - w)) : r + (time % w - w);
}
// y좌표도 동일하게 이동 처리
if (time / h % 2 == 0) {
c = c + (time % h) > h ? h - (c + (time % h) - h) : c + (time % h);
} else {
c = c + (time % h - h) < 0 ? - (c + (time % h - h)) : c + (time % h - h);
}
System.out.println(r + " " + c);
}
}
개선 사항
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] size = br.readLine().split(" ");
int w = Integer.parseInt(size[0]);
int h = Integer.parseInt(size[1]);
String[] point = br.readLine().split(" ");
int p = Integer.parseInt(point[0]);
int q = Integer.parseInt(point[1]);
int t = Integer.parseInt(br.readLine());
int x = (t + p) % (2 * w);
int y = (t + q) % (2 * h);
if (x > w) {
x = 2 * w - x;
}
if (y > h) {
y = 2 * h - y;
}
System.out.println(x + " " + y);
}
}- x, y좌표의 계산을 매우 간결하게 처리했다.
- x, y좌표가 범위를 넘었을 경우를 별도 if문으로 처리하여 가독성이 좋아졌다.
문제에 좌표가 있으면 일단 무조건 배열을 생성하고
시간별로 일일이 처리하도록 계산했었는데,
이렇게 간단한 계산식으로 처리할 수가 있다는 것을
바로 생각해내지 못했다.
항상 정해진 답은 없다는 것을 생각하고
더 효율적인 방법이 있을지 생각해봐야 하겠다.