[백준] 17143.낚시왕 (java) / 시뮬레이션

@시뮬레이션 / 1h 4m

5달 전에 처음 풀었을때는 5시간 넘게 풀었는데도 결국 실패했는데

이번에는 한시간만에 풀어서 뿌듯했다ㅎㅎ

 

 

문제 링크

https://www.acmicpc.net/problem/17143

17143번: 낚시왕

 

 

구현 포인트

사실 시뮬레이션 문제에서 가장 중요한 점은

문제에서 시키는 대로 하기

이다.

 

 

문제를 읽다가 더 효율적인 방법이 떠오른다 해도, 일단 기본은 문제에서 시키는대로 해야한다.

백준 나무 재테크 같은 문제도, 이 문제도 그게 포인트다.

 

문제 설명을 보면 이렇게 나와있다.

 

그래서 문제와 똑같이

while (낚시왕이 가장 오른쪽 열의 오른쪽 칸에 도착하기 전까지) {

     낚시왕의 y좌표++;

     상어 잡기();

     상어들 이동시키기();

}

이렇게 구현하면 된다.

 

 

그런데 이 문제의 복병은 시간초과 인데

처음 풀었을 때에는 수학적으로 계산해서 한칸씩 이동하는게 아니라, 벽에 닿을 때를 미리 계산해서 풀려고 했다.

그러다가 시간도 터지고 내 머리도 터져서 결국 못 풀었다.

 

이번에는, 그렇게 하면 답이 없다는걸 생각하면서 다른 방법을 떠올렸다.

포인트는, 상어가 제자리로 돌아오려면 얼마나 걸리는지 였다.

이 그림에서, (4,1)의 A 상어가 제자리로 돌아오는데에는 속력 10이 필요하다.

즉, 10, 20, 30... 이 10의 배수만큼 이동하면 상어는 늘 제자리로 돌아온다.

여기서 10은 (총 열의 크기인 6 - 1) * 2 로 생각할 수 있다.

 

즉, 좌 또는 우로 이동하는 상어는, 상어의 속력 % ((열의크기 - 1) * 2) 만큼만 이동하면 되고,

상 또는 하로 이동하는 상어는 상어의 속력 % ((행의크기 - 1) * 2) 만큼만 이동하면 된다.

 

이 코드를 추가하니까 바로 시간초과 문제가 해결됐다.

 

 

구현 방법

1. 이렇게 이동하면서 겹치는 경우에 다른 상어를 먹는 형태의 문제는

맵을 두개 써서 풀면 편하다.

 

나는 주로 맵을 두개 만들어 놓고 이렇게 푸는 방식을 선호한다.

if (idx % 2 == 0) 이면

     함수(map1, map2);

else

     함수(map2, map1);

 

이 때, 포인트는 두 가지이다.

1) 이동하고 나서 이전 자리를 지워주는 것

2) 겹친 경우를 대비하여 큐에서 뺐을 때 map의 값과 큐의 사이즈가 같지 않을 경우 continue;

 

 

2. 벽에 부딪히면 반대 방향으로 가는 방법

생각보다 이런 문제가 많다.

나는 0:상 1:좌 2:하 3:우 로 두고 d = (d + 2) % 4; 로 푼다.

이렇게 풀면 따로 if문으로 분기처리를 해 줄 필요가 없다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	private static class Shark {
		int x, y, d, dist, size;

		public Shark(int x, int y) {
			this.x = x;
			this.y = y;
		}
		public Shark(int x, int y, int dist, int d, int size) {
			this(x, y);
			this.dist = dist;
			this.d = d;
			this.size = size;
		}
	}
	
	private static int R, C, M, map1[][], map2[][], sum = 0, sharkCount = 0;
	private static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
	private static Queue<Shark> q = new LinkedList<>();
	
	public static void main(String[] args) throws Exception {
		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());
		
		map1 = new int[R + 1][C + 2];
		map2 = new int[R + 1][C + 2];
		
		int r, c, s, d, z;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			s = Integer.parseInt(st.nextToken());
			d = Integer.parseInt(st.nextToken());
			z = Integer.parseInt(st.nextToken());
			if (d == 1)			d = 0;
			else if (d == 4)	d = 1;
			
			q.add(new Shark(r, c, s, d, z));
			map1[r][c] = z;
		}
		
		int manX = 0;
		while (manX <= C) {
			if (M == 0 || M == sharkCount) break;
			if (manX % 2 == 0) {
				manCatch(++manX, map1);
				fishMove(map1, map2);
			} else {
				manCatch(++manX, map2);
				fishMove(map2, map1);
			}
		}
		System.out.println(sum);
	}

	private static void fishMove(int[][] prev, int[][] now) {
		int size = q.size();
		for (int i = 0; i < size; i++) {
			Shark temp = q.poll();
			if (prev[temp.x][temp.y] != temp.size) continue;
			oneMove(temp, now);
			prev[temp.x][temp.y] = 0;
		}
	}

	private static void oneMove(Shark temp, int[][] now) {
		int nx = temp.x, ny = temp.y, d = temp.d, dist = temp.dist, size = temp.size;
		
		if (d == 0 || d == 2) dist = dist % ((R - 1) * 2);
		else dist = dist % ((C - 1) * 2);
		
		for (int i = 0; i < dist; i++) {
			if (nx + dx[d] <= 0 || nx + dx[d] >= R + 1 || ny + dy[d] <= 0 || ny + dy[d] >= C + 1)
				d = (d + 2) % 4;
			
			nx += dx[d];
			ny += dy[d];
		}
		
		//이미 누군가 있는데 그 애가 지금 나보다 크다면 
		if (now[nx][ny] > size) return;
		
		//아무도 없거나, 내가 이전에 있는 애보다 크다면 
		now[nx][ny] = size;
		q.add(new Shark(nx, ny, dist, d, size));
	}

	private static void manCatch(int y, int[][] map) {
		for (int x = 1; x <= R; x++) {
			if (map[x][y] != 0) {
				sum += map[x][y];
				map[x][y] = 0;
				sharkCount++;
				break;
			}
		}
	}
}

 

 

드디어 풀었다.

실력이 예전보다 는 게 느껴져서 뿌듯했다.

 

끝!