백준 17143: 낚시왕
https://www.acmicpc.net/problem/17143
문제 설명
R×C 격자 위에 여러 마리의 상어가 있다.
상어는 각각 속도(s), 방향(d), 크기(z)를 가지고 있으며, 낚시왕은 1열부터 오른쪽으로 한 칸씩 이동하면서 가장 가까운 상어를 낚고, 이후 모든 상어가 동시에 이동한다.
같은 칸에 여러 상어가 도착하면 가장 큰 상어만 살아남는다.
1차 시도 (오답)
import java.io.*;
import java.util.*;
public class Main {
// 상하우좌
static int[] dr = {0, -1, 1, 0, 0};
static int[] dc = {0, 0, 0, 1, -1};
static class Shark {
int r, c, s, d, z;
boolean isAlive;
public Shark(int r, int c, int s, int d, int z) {
super();
this.r = r;
this.c = c;
this.s = s;
this.d = d;
this.z = z;
this.isAlive = true;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] map = new int[R+1][C+1];
Shark[] sharks = new Shark[M+1];
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken()); // 속도
int d = Integer.parseInt(st.nextToken()); // 방향
int z = Integer.parseInt(st.nextToken()); // 크기
sharks[i] = new Shark(r, c, s, d, z);
map[r][c] = i;
}
int ans = 0;
for (int c=1; c<=C; c++) {
// 낚시
for (int r=1; r<=R; r++) {
if (map[r][c] > 0) {
ans += sharks[map[r][c]].z;
sharks[map[r][c]].isAlive = false;
map[r][c] = 0;
break;
}
}
// 상어 이동
for (int i=1; i<=M; i++) {
Shark s = sharks[i];
if (!s.isAlive) continue;
// 이동 위치 계산
int nr = s.r + dr[s.d]*s.s;
int nc = s.c + dc[s.d]*s.s;
while (nr<1 || nr >R || nc<1 || nc>C) {
if (nr<1) {
nr = 1+(1-nr);
s.d = 2;
}
else if (nr>R) {
nr = R-(nr-R);
s.d = 1;
}
else if (nc<1) {
nc = 1+(1-nc);
s.d = 3;
}
else if (nc>C) {
nc = C-(nc-C);
s.d = 4;
}
}
// 겹치는지 확인
if (map[nr][nc] == 0) {
if (map[s.r][s.c] == i) map[s.r][s.c] = 0;
s.r = nr;
s.c = nc;
map[nr][nc] = i;
} else {
// 이미 이동 마친 상어면 진짜 있는거니까 크기 비교
if (map[nr][nc] < i) {
int winner = 0;
int loser = 0;
if (s.z > sharks[map[nr][nc]].z) {
winner = i;
loser = map[nr][nc];
} else {
winner = map[nr][nc];
loser = i;
}
// 사망 처리
sharks[loser].isAlive = false;
// 승자 이동 처리
if (map[sharks[winner].r][sharks[winner].c] == winner) map[s.r][s.c] = 0;
sharks[winner].r = nr;
sharks[winner].c = nc;
map[nr][nc] = winner;
}
// 아니면 그냥 이동해버리기
else {
if (map[s.r][s.c] == i) map[s.r][s.c] = 0;
s.r = nr;
s.c = nc;
map[nr][nc] = i;
}
}
}
}
System.out.println(ans);
}
}
로직
- 초기화
- 상어마다 위치와 속도·방향·크기를 입력받아 Shark 객체로 관리하고,
map 배열에는 그 상어의 번호를 기록했다. - map[r][c] = i → “i번 상어가 (r, c)에 있다”는 의미.
- 상어마다 위치와 속도·방향·크기를 입력받아 Shark 객체로 관리하고,
- 낚시 단계
- 낚시꾼이 오른쪽으로 한 칸 이동할 때마다, 해당 열의 가장 위쪽 상어를 잡고 map[r][c] = 0으로 비워준다.
- 잡힌 상어는 isAlive = false로 표시하고, 크기를 점수에 더한다.
- 상어 이동 단계
- for문으로 모든 상어를 순회하며 map배열 기준으로 이동 처리
- 만약 이동한 칸에 다른 상어가 이미 있으면, 이동 처리한 상어면 그 자리에서 즉시 크기 비교해 큰 상어만 남겼다.
- 이동 처리하지 않은 상어면 그냥 무시하고 이동시켰다
문제는 이동 단계에서 발생했다.
이동 중인 상어가 이미 map을 갱신한 상어의 흔적을 보고 움직이게 된다.
즉, 모든 상어가 동시에 이동해야 하는데, 실제로는 이전 상어의 이동 결과를 보면서 순차 이동하게 되는 구조다. 따라서 같은 입력이라도 “이동 순서”에 따라 결과가 달라질 수 있고,
문제의 요구사항인 **‘동시 이동 후 충돌 판정’**이 깨져버린다.
처음에는 단순하게 map 하나로 모든 단계를 처리하려 했다.
map에 상어 번호를 저장해두고, 낚시 → 이동 → 충돌 처리를 모두 같은 배열에서 진행했다.
이 방식의 장점은 구현이 직관적이라는 점이었지만,
곧 “동시 이동”이라는 조건에서 큰 문제가 생겼다.
- 낚시 시점에서 map[r][c] = 0을 먼저 해서 NPE 발생
- 상어가 “동시에” 이동하지 않고 순차적으로 map을 덮어씀
- 결과적으로 같은 칸에 도착한 상어의 크기 비교가 불완전함
2차 시도 (성공)
1차에서 가장 큰 문제였던 “동시 이동 처리”를 해결하기 위해
새로운 맵(newMap)을 만들어 이동 결과를 저장하도록 수정했다.
이후 이동이 모두 끝나면 map = newMap으로 갱신하도록 했다.
for (int c = 1; c <= C; c++)
// 동시 이동 처리를 위한 map 생성
int[][] newMap = new int[R + 1][C + 1];
// 상어 이동
for (int i = 1; i <= M; i++) {
Shark s = sharks[i];
if (!s.isAlive)
continue;
// 이동 위치 계산
int nr = s.r + dr[s.d] * s.s;
int nc = s.c + dc[s.d] * s.s;
while (nr < 1 || nr > R || nc < 1 || nc > C) {
if (nr < 1) {
nr = 1 + (1 - nr);
s.d = 2;
} else if (nr > R) {
nr = R - (nr - R);
s.d = 1;
} else if (nc < 1) {
nc = 1 + (1 - nc);
s.d = 3;
} else if (nc > C) {
nc = C - (nc - C);
s.d = 4;
}
}
// 겹치는지 확인
if (newMap[nr][nc] == 0) {
newMap[nr][nc] = i;
s.r = nr;
s.c = nc;
} else {
int j = newMap[nr][nc];
if (sharks[j].z > s.z) {
s.isAlive = false;
} else {
newMap[nr][nc] = i;
sharks[j].isAlive = false;
s.r = nr;
s.c = nc;
}
}
// map 갱신
map = newMap;
}
}하지만 여전히 아쉬운 점이 있었다.
이동 처리 시, 상어의 속도가 매우 크면, 벽에 부딪히며 상하 or 좌우로 지나치게 많이 왔다갔다하게 된다.
예를 들어 R=5, s=100이면 1행에 있던 상어가 5행까지 가서 방향 전환, 다시 1행까지 가서 방향 전환, ... 을 수십번 반복해야 한다.
이를 개선하기 위해 규칙을 찾아야 했다.
3차 시도 (개선)
결국 규칙을 찾아 속도 s를 축약했다. 간략히 설명하자면,
C가 4인 상어의 좌우 이동 과정을 쭉 한 줄로 나열했을 때
| 1 | 2 | 3 | 4 | 3 | 2 | 1 | 2 | 3 | 4 | 3 | 2 | 1 |
| 6 | 5 <- | 4 <- | 3 <- | 2 <- | 1 <- | 현재 위치 | -> 1 | -> 2 | -> 3 | -> 4 | -> 5 | 6 |
이다. 이 때, 상어가 2의 위치에서 오른쪽이든 왼쪽이든 다시 제자리로 돌아오려면 몇칸을 이동해야 할까?
=> 6칸이다!
즉 아래와 같이 축약할 수 있다.
- 세로 이동이면 s %= 2*(R-1)
- 가로 이동이면 s %= 2*(C-1)
이렇게 하면 이동 시 실제 필요한 거리만 계산하므로
시간 복잡도를 줄일 수 있다.
입력 시 속도를 축약해 저장해버렸다.
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken()); // 속도
int d = Integer.parseInt(st.nextToken()); // 방향
int z = Integer.parseInt(st.nextToken()); // 크기
// 속도 축약!
if (d==1 || d==2) {
s %= 2*(R-1);
} else {
s %= 2*(C-1);
}
sharks[i] = new Shark(r, c, s, d, z);
map[r][c] = i;
}
결과
결과적으로 2차 시도 대비 3차 시도에서 수행시간을 16% 단축했다!
회고
이 문제는 단순 구현처럼 보여도 “동시 이동 처리”와 “속도 축약”이라는 두 가지 포인트가 있었다.
특히 s가 큰 테스트케이스에서는 시간 초과를 피하려면 왕복 주기 축약이 필요했다.
마치 실버 수준 문제가 여러 개 합쳐져 골드 문제가 된 느낌이였다.
기본기가 필요함을 느꼈다!