[BOJ 17143] 낚시왕

문제

• BOJ 17143
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

SWEA 미생물 격리와 비슷하게 접근할 수 있던 시뮬레이션 문제이다.

1. 현재 맵에 있는 상어 번호를 관리할 map배열, 상어 정보를 관리할 sharks배열이 필요하다.
2. 입력을 받으면서 map에 상어 번호를 인덱스로 정하여 표시하고, 상어정보를 생성한다.
   여기서 주의할 점은 나중에 상어 속력만큼 상어를 이동시키면 속력이 최대 1000이기 때문에 시간초과가 발생한다.
   따라서, 같은 작업을 반복하기 위해 속력의 절반만큼 이동해주도록 다음 코드를 추가하였다.
   이 코드를 처리해주는 것이 이 문제의 포인트였음!!!

    if (d <= 2) s %= ((R - 1) * 2);
    if (d >= 3) s %= ((C - 1) * 2);
   

3. 낚시왕을 한열씩 증가시키면서 다음 작업을 수행한다.
   3-1. 상어 찾기
   (1) 현재 열에서 행을 증가시키면서 상어를 찾으면 이 상어의 크기를 Ans에 더하고 상어를 삭제한다.
   3-2. 모든 상어 이동시키기
   (1) 이동 전, 현재 상어의 흔적을 남기지 않기 위해 map배열을 초기화시키고 모든 상어를 이동시킨다.
   다음 좌표에서 벽을 만나면 changeDir()함수를 호출해서 방향을 반대로 바꿔준다.
   (2) 이동한 좌표에 이미 다른 상어가 있다면 더 큰 상어를 넣고, 작은 쪽의 상어는 삭제해준다.
   (3) sharks배열에 이동 후의 상어 정보를 갱신해준다.

시간초과가 계속 나서 결국 검색 후에 속력을 필터링해주는 작업이 필요하다는 것을 깨달았다.
만약, 실제 시험이었다면 맞은줄 알았겠지만 백퍼 틀렸을 것이다 (ㅠㅠ)
실제 시험에서도 이런 아이디어를 생각할 수 있도록 시간복잡도를 미리 계산해보는 습관이 필요하다는것을 깨달았다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[][] map;
	static Shark[] sharks;
	static int R, C, M; // 격자판의 크기, 상어의 수
	static int Ans; // 낚시왕이 잡은 상어 크기의 합
	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;

		public Shark(int r, int c, int s, int d, int z) {
			this.r = r;
			this.c = c;
			this.s = s;
			this.d = d;
			this.z = z;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[R + 1][C + 1];
		sharks = new Shark[M + 1]; // 1번 상어~M번 상어
		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 <= 2) s %= ((R - 1) * 2);
			if (d >= 3) s %= ((C - 1) * 2);

			sharks[i] = new Shark(r, c, s, d, z);
			map[r][c] = i;
		}

		if (M != 0) {
			int nowCol = 0;
			while (nowCol++ < C) { // C열까지 한칸씩 움직임
				// 1. 현재 열에서 행을 증가시키면서 상어 찾기
				for (int r = 1; r <= R; r++) {
					if (map[r][nowCol] != 0) { // 상어 찾으면
						Shark shark = sharks[map[r][nowCol]];
						Ans += shark.z;
						sharks[map[r][nowCol]] = null;
						map[r][nowCol] = 0; // 상어 삭제
						break;
					}
				}

				map = new int[R + 1][C + 1];

				// 2. 상어 이동
				for (int i = 1; i <= M; i++) {
					if (sharks[i] == null) continue;
					Shark shark = sharks[i];

					int cnt = 0;
					while (cnt++ < shark.s) { // 상어의 속력만큼 칸 이동
						int nr = shark.r + dr[shark.d];
						int nc = shark.c + dc[shark.d];
						if (nr < 1 || nr > R || nc < 1 || nc > C) {
							shark.d = changeDir(shark.d); // 방향을 반대로 바꿈
							nr = shark.r + dr[shark.d]; // 반대 방향으로 이동
							nc = shark.c + dc[shark.d];
						}
						shark.r = nr;
						shark.c = nc;
					} // 이동 끝
					if (map[shark.r][shark.c] != 0) {
						if (sharks[map[shark.r][shark.c]].z > shark.z) { // 원래 상어가 더 크다면
							sharks[i] = null;
							continue;
						} else sharks[map[shark.r][shark.c]] = null;
					}
					map[shark.r][shark.c] = i;
					sharks[i] = shark;
				}
			}
		}
		System.out.println(Ans);
	}

	static public int changeDir(int dir) {
		switch (dir) {
		case 1: // 상
			dir = 2;
			break;
		case 2: // 하
			dir = 1;
			break;
		case 3: // 우
			dir = 4;
			break;
		case 4: // 좌
			dir = 3;
			break;
		}
		return dir;
	}
}