김무성

김무성

2020.11.18 ~

[백준] 17143. 낚시왕

5 분 소요

문제 링크

[백준] 17143. 낚시왕


풀이 과정

시뮬레이션 문제입니다.

작성한 코드는 다음과 같은 매커니즘으로 동작합니다.

  1. 상어를 잡는다.
  2. 상어들을 이동시킨다.
  3. 낚시왕을 오른쪽 열로 한 칸 이동시킨다.


map = new Shark[R + 1][C + 1];
sharks = new Shark[M + 1];
movedSharks = new HashMap<>();

사용한 자료구조는 위와 같습니다.

  • 2차원 배열 map : 상어가 위치한 좌표에 상어의 모든 정보를 담아 Shark 객체로 만들어 저장한다.
  • 1차원 배열 sharks : 존재하는 각 상어의 모든 정보를 담아 Shark 객체로 만들어 저장한다.
  • HashMap movedSharks : 상어가 이동한 좌표를 key로, 변경된 상어 정보를 담는 Shark 객체를 value로 저장한다.


for (int i = 1; i <= M; i++) {
    st = new StringTokenizer(br.readLine());
    int r, c, s, d, z;
    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());

    s = (d == 1 || d == 2) ? s % (2 * (R - 1)) : s % (2 * (C - 1));

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

상어의 정보는 총 다섯 가지입니다.

  • r, c : 상어의 좌표
  • s : 상어의 속도
  • d : 상어의 이동 방향
  • z : 상어의 크기

상어의 정보를 입력받아 map과 sharks 에 각각 저장합니다. 이 때, 상어의 속도 s 는 상어의 이동 방향이 가로인 경우와 세로인 경우로 나누어 제자리로 돌아오는 로테이션을 최대한 제거해줍니다.


예를 들어, 속도가 18인 상어는 10초 뒤에 처음과 같은 이동 방향을 유지한 채 처음 자리에 위치하게 됩니다. 따라서, 초기 위치로 돌아오는 모든 사이클을 미리 다 배제하도록 속도를 조정해줍니다.


상어의 이동 방향이 가로 방향인 경우는 2 * (C - 1) 초 뒤에, 세로 방향인 경우는 2 * (R - 1) 초 뒤에 초기 이동 방향을 유지한 채 제자리로 돌아오게 됩니다. 따라서, 모듈러 연산을 통해 상어의 이동 속도 s 를 조정해준 뒤, 변경된 s로 객체를 생성합니다.


for (int j = 1; j <= C; j++) {
    fishing(j);
    move();
}

이제 낚시왕을 한 칸씩 오른쪽으로 이동시키며 상어를 잡고( fishing 메소드 ), 상어를 이동( move 메소드 )시킵니다.


static void fishing(int now) {
    Shark target = null;

    for (int i = 1; i <= R; i++) {
        if (map[i][now] == null) continue;

        target = map[i][now];
        break;
    }

    if (target == null) return;

    answer += target.z;

    sharks[target.idx] = null;
    map[target.x][target.y] = null;
}

fishing 메소드 는 now 열에서 지상으로부터 가장 가까운 상어를 잡는 동작을 수행합니다. 잡고난 뒤에는, 배열 sharks 와 map 에서 해당 상어를 null 처리함으로써 제거합니다.


static void move() {
    movedSharks.clear();

    for (int i = 1; i <= M; i++) {
        Shark target = sharks[i];

        if (target == null) continue;

        int[] movedPosDir = getMovedPosDir(target);
        Shark movedShark = new Shark(target.idx, movedPosDir[0], movedPosDir[1], target.s, movedPosDir[2], target.z);
        Point key = new Point(movedPosDir[0], movedPosDir[1]);

        if (movedSharks.containsKey(key)) {
            Shark origin = movedSharks.get(key);

            if (origin.z < movedShark.z) {
                movedSharks.put(key, movedShark);
                sharks[origin.idx] = null;
            } else {
                sharks[movedShark.idx] = null;
            }
        } else {
            movedSharks.put(key, movedShark);
        }

        map[target.x][target.y] = null;
    }

    for (Map.Entry<Point, Shark> entry : movedSharks.entrySet()) {
        Point key = entry.getKey();
        Shark val = entry.getValue();

        map[key.x][key.y] = val;
        sharks[val.idx] = val;
    }
}

move 메소드 는 모든 상어들을 이동시킨 뒤, 같은 좌표에 여러 마리의 상어가 있을 경우, 크기가 가장 큰 상어를 남겨두는 동작을 수행합니다.

  1. 상어를 저장해 둔 배열 sharks 를 순회하며, 상어가 잡혔거나 먹혀 null 처리된 경우면 패스합니다.
  2. getMovedPosDir 메소드 를 통해 상어를 이동시킨 뒤의 좌표와 방향을 얻어옵니다.
  3. 이동된 상어의 새로운 정보들로 movedShark 라는 새로운 객체를 만들고, HashMap의 contains 연산을 위한 Point 객체도 생성합니다.(int[] 로는 정확한 객체 동등 연산이 안되므로 내장 클래스 Point 를 사용했습니다.)
    • 이동한 상어들을 담고 있는 HashMap movedSharks 에 이미 해당 좌표(key)로 개체가 존재한다면, 크기가 더 큰 상어를 남겨두고 다른 하나를 제거합니다.
    • 좌표(key)가 존재하지 않을 시, 해당 좌표에는 상어가 존재하지 않으므로 그냥 넣어줍니다.
  4. 2차원 배열에서 이동된 상어의 원래 좌표를 null 처리해 제거해줍니다.
  5. movedSharks 에 담겨있는 이동된 상어들의 정보를 map 과 sharks 에 반영해줍니다.


코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int R, C, M;
    static Shark[][] map;
    static Shark[] sharks;
    static HashMap<Point, Shark> movedSharks;
    static int[] dx = {0, -1, 1, 0, 0}, dy = {0, 0, 0, 1, -1};
    static int answer;

    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());

        map = new Shark[R + 1][C + 1];
        sharks = new Shark[M + 1];
        movedSharks = new HashMap<>();

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int r, c, s, d, z;
            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());

            s = (d == 1 || d == 2) ? s % (2 * (R - 1)) : s % (2 * (C - 1));

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

        for (int j = 1; j <= C; j++) {
            fishing(j);
            move();
        }

        System.out.println(answer);
    }

    static void fishing(int now) {
        Shark target = null;

        for (int i = 1; i <= R; i++) {
            if (map[i][now] == null) continue;

            target = map[i][now];
            break;
        }

        if (target == null) return;

        answer += target.z;

        sharks[target.idx] = null;
        map[target.x][target.y] = null;
    }

    static void move() {
        movedSharks.clear();

        for (int i = 1; i <= M; i++) {
            Shark target = sharks[i];

            if (target == null) continue;

            int[] movedPosDir = getMovedPosDir(target);
            Shark movedShark = new Shark(target.idx, movedPosDir[0], movedPosDir[1], target.s, movedPosDir[2], target.z);
            Point key = new Point(movedPosDir[0], movedPosDir[1]);

            if (movedSharks.containsKey(key)) {
                Shark origin = movedSharks.get(key);

                if (origin.z < movedShark.z) {
                    movedSharks.put(key, movedShark);
                    sharks[origin.idx] = null;
                } else {
                    sharks[movedShark.idx] = null;
                }
            } else {
                movedSharks.put(key, movedShark);
            }

            map[target.x][target.y] = null;
        }

        for (Map.Entry<Point, Shark> entry : movedSharks.entrySet()) {
            Point key = entry.getKey();
            Shark val = entry.getValue();

            map[key.x][key.y] = val;
            sharks[val.idx] = val;
        }
    }

    static int[] getMovedPosDir(Shark shark) {
        int speed = shark.s;
        int x = shark.x, y = shark.y;
        int dir = shark.d;

        while (speed-- > 0) {
            int nx = x + dx[dir], ny = y + dy[dir];

            if (!inRange(nx, ny)) {
                dir = changeDir(dir);
                x = x + dx[dir];
                y = y + dy[dir];
            } else {
                x = nx;
                y = ny;
            }
        }

        return new int[]{x, y, dir};
    }

    static int changeDir(int dir) {
        if (dir == 1) return 2;
        else if (dir == 2) return 1;
        else if (dir == 3) return 4;
        else return 3;
    }

    static boolean inRange(int x, int y) {
        return x >= 1 && x <= R && y >= 1 && y <= C;
    }

    static class Shark {
        int idx;
        int x, y, s, d, z;

        public Shark(int idx, int x, int y, int s, int d, int z) {
            this.idx = idx;
            this.x = x;
            this.y = y;
            this.s = s;
            this.d = d;
            this.z = z;
        }
    }
}

카테고리:

업데이트:

댓글남기기

참고