Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 그래프
- 트러블슈팅
- 싸피
- 완전탐색
- 완탐
- JPA
- Spring
- 다시보기
- 자바
- 알고리즘
- SSAFY
- 다익스트라
- BFS
- 코테
- DFS
- Java
- database
- 부분수열의합2
- 그리디
- Union Find
- 코딩테스트
- 코딩테스트실력진단
- 알고리즘기본개념
- SWEA
- DP
- 코드트리
- 기본유형
- JUnit
- 백준
- 유니온파인드
Archives
- Today
- Total
HwangHub
[Java/시뮬레이션] 백준 17143. 낚시왕 본문
🤔 Intuition
시뮬레이션 문제인데, 1월부터 4월까지 오랜 기간에 걸쳐 총 3번의 시도 끝에 성공했다.
다시 도전해서 드디어 성공했다...
이 문제는 상어가 움직이는 걸 수식으로 구현하는 게 포인트이다. (이걸 그냥 단순 반복으로 한칸한칸 움직이게 구현하면 시간초과 발생, 근데 또 수식으로 구현하려니 머리 아픔)
옛날에는 애초에 시뮬레이션 문제를 잘 못풀었고, 2트 째에는 수식 완성을 못했다. 그리고 3트 째에 드디어 풀었다...
🔎 Algorithm & Complexity
* @algorithm simulation
* @time O(R*C*C) : 532 ms
* @memory O(R*C) : 30504 KB
👨🏻💻 Logic
- 각 column 상 가장 위에 있는 상어를 낚는다.
- 상어를 움직인다. 이 때, R-1, C-1 의 두 배를 기준으로 상어는 같은 위치로 돌아오므로 이를 mod 연산을 이용하여 처리해준다. 그 이후 방향이 바뀌는 경우와 아닌 경우를 나눠서 움직이는 위치를 구한다.
- 움직이는 위치에 이미 상어가 있는 경우에는 더 큰 놈만 살려둔다.
public class BOJ_17143_낚시왕 {
private static int R, C, M, r,c,s,d,z,nr,nc;
private static int[] dr = {0, -1, 1, 0, 0}; // 상 하 우 좌
private static int[] dc = {0, 0, 0, 1, -1};
public static final int UP = 1;
public static final int DOWN = 2;
public static final int RIGHT = 3;
public static final int LEFT = 4;
private static PriorityQueue<Shark>[] sharks;
private static Shark[][] temp;
private static class Shark {
private int row, col, speed, direction, size;
private Shark(int r, int c, int s, int d, int z) {
row = r;
col = c;
speed = s;
direction = d;
size = z;
}
}
private static class Pair {
int idx;
Shark shark;
private Pair(int idx, Shark shark) {
this.idx = idx;
this.shark = shark;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
sharks = new PriorityQueue[C];
for (int i = 0; i < C; i++) {
sharks[i] = new PriorityQueue<>(Comparator.comparingInt(o -> o.row));
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken()) - 1;
c = Integer.parseInt(st.nextToken()) - 1;
s = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
z = Integer.parseInt(st.nextToken());
sharks[c].add(new Shark(r, c, s, d, z));
}
int ans = 0;
for (int fisherIdx = 0; fisherIdx < C; fisherIdx++) { // 낚시왕이 움직이는 횟수만큼
// 상어 하나 낚기
if (!sharks[fisherIdx].isEmpty()) {
// System.out.println("sharks[fisherIdx].peek().size = " + sharks[fisherIdx].peek().size);
ans += sharks[fisherIdx].poll().size;
}
// 상어 이동하기
temp = new Shark[R][C];
List<Pair> delList = new ArrayList<>();
for (int i = 0; i < C; i++) {
for (Shark shark : sharks[i]) {
r = shark.row;
c = shark.col;
s = shark.speed;
d = shark.direction;
z = shark.size;
nr = r + dr[d]*s;
nc = c + dc[d]*s;
if (d == DOWN) {
if (nr >= R) {
nr = (nr - R) % ((R - 1) * 2);
if (nr >= R - 1) {
nr = nr - (R - 1) + 1;
} else {
nr = (R - 1) - (nr + 1);
shark.direction = UP;
}
}
} else if (d == UP) {
if (nr < 0) {
nr = (Math.abs(nr) - 1) % ((R - 1) * 2);
if (nr >= R - 1) {
nr = (R - 1) - (nr - (R - 1)) - 1;
} else {
nr = nr + 1;
shark.direction = DOWN;
}
}
} else if (d == RIGHT) {
if (nc >= C) {
nc = (nc - C) % ((C - 1) * 2);
if (nc >= C - 1) {
nc = nc - (C - 1) + 1;
} else {
nc = (C - 1) - (nc + 1);
shark.direction = LEFT;
}
}
} else if (d == LEFT) {
if (nc < 0) {
nc = (Math.abs(nc) - 1) % ((C - 1) * 2);
if (nc >= C - 1) {
nc = (C - 1) - (nc - (C - 1)) - 1;
} else {
nc = nc + 1;
shark.direction = RIGHT;
}
}
}
// 위치가 구해졌으니 상어 잡아먹기 진행
if (temp[nr][nc] != null) {
if (temp[nr][nc].size > shark.size) {
continue;
}
}
temp[nr][nc] = shark;
}
}
for (int i = 0; i < C; i++) {
sharks[i].clear();
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
// System.out.print(temp[i][j] == null ? "0 " : temp[i][j].size + " ");
if (temp[i][j] != null) {
temp[i][j].row = i;
temp[i][j].col = j;
sharks[j].add(temp[i][j]);
}
}
// System.out.println();
}
// System.out.println("---------------");
}
System.out.println(ans);
}
}
'workspace > 알고리즘' 카테고리의 다른 글
[Java/플로이드워셜] SWEA. 키 순서 (0) | 2024.04.03 |
---|---|
[Java/시뮬레이션] SWEA. 벽돌깨기 (0) | 2024.04.03 |
[Java/다익스트라] 백준 4485. 녹색 옷 입은 애가 젤다지? (0) | 2024.04.02 |
[Java/수학] SWEA. 원점으로 집합 (1) | 2024.04.02 |
[Java/투포인터] LeetCode 992. Subarrays with K Different Integers (0) | 2024.03.30 |