들어가며
https://www.acmicpc.net/problem/17143
정석적인 시뮬레이션 문제다. 문제를 읽고 필요한 풀이를 직관적으로 정리하자면
1. 상어잡기
2. 상어 이동
3. 이동 할때 두마리 이상의 상어가 있다면 서로 싸워라.
본문으로
딱 읽었을 때 익숙한 느낌의 좌표 이동 시키고~ 없애고~ 하는 식의 시뮬레이션 문제였다. 상어 잡는 로직과 상어 이동하는 로직을 신경써서 아래와 같이 작성했다.
public class Main {
static int ret, Y, X, M;
static class Shark {
int s;
int d;
int z;
Shark(int s, int d, int z) {
this.s = s;
this.d = d;
this.z = z;
}
}
static class After {
int h;
int d;
After(int h, int d) {
this.h = h;
this.d = d;
}
}
static Shark[][] makeMap(Shark[][] maps) {
Shark[][] dMaps = new Shark[Y][X];
for (int i = 0; i < Y; i++) {
for (int j = 0; j < X; j++) {
if (maps[i][j] != null) {
Shark shark = maps[i][j];
if (shark.d <= 2) { // 위 아래
After after = goY(i, shark.s, shark.d);
shark.d = after.d;
if (dMaps[after.h][j] != null) {
if (dMaps[after.h][j].z < shark.z) {
dMaps[after.h][j] = shark;
}
} else {
dMaps[after.h][j] = shark;
}
} else { // 좌우
After after = goX(j, shark.s, shark.d);
shark.d = after.d;
if (dMaps[i][after.h] != null) {
if (dMaps[i][after.h].z < shark.z) {
dMaps[i][after.h] = shark;
}
} else {
dMaps[i][after.h] = shark;
}
}
}
}
}
return dMaps;
}
static After goY(int here, int s, int d) {
while (s > 0) {
if (d == 1) { // 위
if (here - 1 < 0) {
d = 2;
continue;
}
here--;
} else { // 2 -> 아래
if (here + 1 >= Y) {
d = 1;
continue;
}
here++;
}
s--;
}
return new After(here, d);
}
static After goX(int here, int s, int d) {
while (s > 0) {
if (d == 3) { // -> 오른쪽
if (here + 1 >= X) {
d = 4;
continue;
}
here++;
} else { // 4 -> 왼쪽
if (here - 1 < 0) {
d = 3;
continue;
}
here--;
}
s--;
}
return new After(here, d);
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
Y = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
Shark[][] maps = new Shark[Y][X];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken()) - 1;
int x = Integer.parseInt(st.nextToken()) - 1;
int s = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int z = Integer.parseInt(st.nextToken());
maps[y][x] = new Shark(s, d, z);
}
ret = 0;
// 왼 -> 오
for (int i = 0; i < X; i++) {
// 현재 x에서 땅과 가장 가까운 상어잡기
for (int j = 0; j < Y; j++) {
if (maps[j][i] != null) {
ret += maps[j][i].z;
maps[j][i] = null;
break; // 잡으면 바로 넘어가기
}
}
// 상어 이동
maps = makeMap(maps);
}
System.out.println(ret);
}
}
풀고 나서,, 다른 분들의 풀이를 참고했는데 너무 괜찮은 사고가 있어서 정리하려고 한다.
이전의 로직은 상어가 벽을 만났을 때 방향을 바꿔 이동하는 것을 실제로 다 구현했었다.(벽을 만날때까지 실제로 이동했다는 뜻)
사실 상어의 이동 후 위치 결과가 중요하지, 이동 과정은 중요하지 않기 때문에 왔다갔다 하는 것을 실제로 왔다갔다 할 필요가 없다는 것이다.
아래와 같은 좌표에서 0에서 시작한다고 할때, 튕기면서 이동한다는 것을 확인할 수 있다.
0 1 2 3
// 아래와 같은 식으로 튕기면서 움직일 것.
0 -> 1 -> 2 -> 3 -> 2 -> 1 -> 0 -> 1 -> 2 -> 3 ...당연한 말이지만, 0칸에서 (R-1)칸 까지 가려면 R-1칸을 이동해야 한다. 8칸을 간다고 치면 왔다갔다 한번 하고 2칸을 앞으로 가기만 하면 된다. 이를 즉 실제로 이동할 거리를 s %= 2 * (R - 1) 로 정리할 수 있다. 아래는 이 최적화 식을 적용한 코드이다.
public class Main {
static int ret, Y, X, M;
static class Shark {
int s;
int d;
int z;
Shark(int s, int d, int z) {
this.s = s;
this.d = d;
this.z = z;
}
}
static class After {
int h;
int d;
After(int h, int d) {
this.h = h;
this.d = d;
}
}
static Shark[][] makeMap(Shark[][] maps) {
Shark[][] dMaps = new Shark[Y][X];
for (int i = 0; i < Y; i++) {
for (int j = 0; j < X; j++) {
if (maps[i][j] != null) {
Shark shark = maps[i][j];
if (shark.d <= 2) { // 위 아래
After after = goY(i, shark.s, shark.d);
shark.d = after.d;
if (dMaps[after.h][j] != null) {
if (dMaps[after.h][j].z < shark.z) {
dMaps[after.h][j] = shark;
}
} else {
dMaps[after.h][j] = shark;
}
} else { // 좌우
After after = goX(j, shark.s, shark.d);
shark.d = after.d;
if (dMaps[i][after.h] != null) {
if (dMaps[i][after.h].z < shark.z) {
dMaps[i][after.h] = shark;
}
} else {
dMaps[i][after.h] = shark;
}
}
}
}
}
return dMaps;
}
static After goY(int here, int s, int d) {
while (s-- > 0) {
if (d == 1) { // 위
if (here - 1 < 0) {
d = 2;
here++;
} else {
here--;
}
} else { // 2 -> 아래
if (here + 1 >= Y) {
d = 1;
here--;
} else {
here++;
}
}
}
return new After(here, d);
}
static After goX(int here, int s, int d) {
while (s-- > 0) {
if (d == 3) { // -> 오른쪽
if (here + 1 >= X) {
d = 4;
here--;
} else {
here++;
}
} else { // 4 -> 왼쪽
if (here - 1 < 0) {
d = 3;
here++;
} else {
here--;
}
}
}
return new After(here, d);
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
Y = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
Shark[][] maps = new Shark[Y][X];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken()) - 1;
int x = Integer.parseInt(st.nextToken()) - 1;
int s = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int z = Integer.parseInt(st.nextToken());
// 속력 주기 최적화
if (d == 1 || d == 2) {
if (Y > 1) {
s %= (2 * (Y - 1));
}
} else if (d == 3 || d == 4) {
if (X > 1) {
s %= (2 * (X - 1));
}
}
maps[y][x] = new Shark(s, d, z);
}
ret = 0;
// 왼 -> 오
for (int i = 0; i < X; i++) {
// 현재 x에서 땅과 가장 가까운 상어잡기
for (int j = 0; j < Y; j++) {
if (maps[j][i] != null) {
ret += maps[j][i].z;
maps[j][i] = null;
break; // 잡으면 바로 넘어가기
}
}
// 상어 이동
maps = makeMap(maps);
}
System.out.println(ret);
}
}
전의 코드와 시간이 확 줄었음을 확인 할 수 있다!!
마무리하며
문제를 그대로 믿고 벽을 만날 때까지 직접가버리니... 시간복잡도가 매우 증가한다.. 실제로 앞으로 2칸만 가면 되는 것을 내 코드는 500번 왕복 후 앞으로 두번 가고 있던 것이었다...
우여곡절로 정답 코드를 내긴 했지만, 조금 더 여유롭게 이런 풀이도 적용할 수 있으면 참 좋겠다.
앞으로도 왕복하는 문제가 있다면 (이동거리) %= 2 * (전체거리 -1) 이런 식의 Thinking을 꼭 생각하자!
'Problem Solve' 카테고리의 다른 글
| [JAVA] 2632 - 피자판매 💛2 : 값이 아닌 경우의 수를 저장하자. + 원형 자료구조는 선형 자료구조로 피자! (0) | 2026.04.15 |
|---|---|
| [JAVA] 15685 - 드래곤 커브 💛3: 기하 문제라면 당황하지 말고 규칙을 찾아보자. (0) | 2026.04.14 |
| [JAVA] 17825 - 주사위 윷놀이 💛2: 한땀한땀 만들어야하는 시뮬레이션 문제(집중하자...) (0) | 2026.04.07 |
| [JAVA] 15662 - 톱니바퀴 (2) 💛5: 역할을 확실하게 나누자..! - 시뮬레이션 정복기 (0) | 2026.04.01 |
| [JAVA] 17406 - 배열 돌리기 4 💛4 : 복잡한 2차원 배열 문제는 복잡도를 줄이기 위해 1차원으로 뽑자! (0) | 2026.03.31 |