백준 17143 낚시왕 자바(java)

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

17143번: 낚시왕

 

풀이 방법

구현, 시뮬레이션 문제이다.

상어는 Shark 클래스를 생성하여 객체로 관리할 수 있도록 하며 Shark 객체를 저장할 2차원 배열 격자판을 생성한다. 주어진 순서대로 낚시왕을 오른쪽으로 이동시키면서 상어를 잡은 후 이동시켜주면 된다.

상어를 잡을 땐 가장 가까운 상어를 잡으므로 행을 위에서부터 탐색하면서 처음 만나는 상어를 잡고 그 위치를 null 로 바꾸어 주어 잡힌 상어를 없앤다.

 

이 문제에서 가장 생각해야 할 것은 상어의 이동이다.

먼저, 격자판에 있는 상어들을 큐에 집어넣고 큐에서 다시 하나씩 빼내어 상어들을 각각 이동시켜준다.

만약, 상어를 한 칸씩 반복문으로 이동시키면 시간 초과가 일어날 것이기 때문에 어떤 규칙을 찾아서 효율적으로 상어를 이동시켜야 한다. 상어가 이동하여 원래의 자리에 원래의 방향으로 다시 위치하면 처음의 상태에서 다시 시작하는 것과 같으므로 그 동안의 이동 횟수는 빼주기만 하면 된다. 그림을 보자. 

 

4열에 있고 왼쪽 방향을 가진 상어가 처음의 상태로 다시 돌아오려면

x만큼 왼쪽으로,  x만큼 오른쪽으로, y만큼 오른쪽으로, y만큼 왼쪽 이동을 한다.

즉, (x+y) x 2 만큼을 이동하였다. 여기서 위의 경우 x+y는 5가 된다. 즉, C개의 열일 때 상어는 (C-1) x 2 만큼 이동하여 다시 처음의 상태로 돌아온다. 마찬가지로 행일 때는 (R-1) x 2 이다.

따라서 상어의 속도를 (C-1) x 2 로 나누어 주고 난 나머지만큼만 직접 한 칸씩 반복문으로 상어를 이동시키면 된다.

 

주의할 것

상어를 이동시킬 때 2차원 배열 격자판은 초기화를 시킨 후 이동시켜야 한다.

상어는 다같이 한번에 이동하므로 이전에 상어들이 있었던 위치는 현재 상어의 이동에 영향을 주면 안되기 때문이다. 초기화를 하지 않고 했다가 현재 상어가 이동한 위치가 이전 상어의 위치 (이 상어도 이동하였으니까 원래는 상어가 없는 곳인데..) 와 겹치면 잡아 먹도록 하여 틀렸다.

 

코드

import java.io.*;
import java.util.*;

public class Main {

    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;
        }
    }

    static int R;
    static int C;
    static int M;
    static Shark[][] board;
    static int[] dr = {0, -1, 1, 0, 0};
    static int[] dc = {0, 0, 0, 1, -1};
    static int answer = 0;

    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());
        board = new Shark[R+1][C+1];

        // 상어 입력
        for(int i=0; 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());
            board[r][c] = new Shark(r, c, s, d, z);
        }

        for(int i=1; i<=C; i++) {
            catchShark(i); // 잡기
            moveSharks(); // 이동
        }
        System.out.println(answer);
    }

    public static void catchShark(int c) {
        for(int i=1; i<=R; i++) {
            if(board[i][c] != null) {
                answer += board[i][c].z;
                board[i][c] = null;
                break;
            }
        }
    }

    public static void moveSharks() {
        Queue<Shark> sharks = new LinkedList<>();
        for(int i=1; i<=R; i++) {
            for(int j=1; j<=C; j++) {
                if(board[i][j] != null) sharks.add(board[i][j]);
            }
        }
        board = new Shark[R+1][C+1]; // 주의! 꼭 초기화 필요

        while(!sharks.isEmpty()) {
            Shark shark = sharks.poll();

            int speed = shark.s;
            if(shark.d <= 2) {
                speed %= (R-1) * 2;
            } else {
                speed %= (C-1) * 2;
            }

            while(speed > 0) {
                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 = (shark.d == 1 || shark.d == 3) ? shark.d + 1: shark.d - 1; // 방향 바꾸기
                    shark.r += dr[shark.d];
                    shark.c += dc[shark.d];
                } else {
                    shark.r = nr;
                    shark.c = nc;
                }
                speed--;
            }

            if(board[shark.r][shark.c] != null) { // 이미 상어가 있는 자리면
                // 이미 있던 상어의 크기가 더 크면 이동 x
                if(board[shark.r][shark.c].z > shark.z) {
                    continue;
                }
            }
            board[shark.r][shark.c] = shark;
        }
    }
}