[JAVA] BOJ 백준 17143번 - 낚시왕

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

17143번: 낚시왕

---

2. 내가 푼 방법

상어를 이동시킬 때 실수를 할 수 있는 문제이다. (( 내가 그랬기 때문에..

 

우선 각각 다른 상어 번호를 지정하여 상어의 정보는 map에 저장했고, 칸에는 최대 한 마리의 상어가 존재하므로 arr 배열에 상어의 번호를 저장했다. 그 후, 낚시왕이 각 열을 지날 때마다 상어를 잡는 fishing 함수와 상어를 이동시키는 move 함수를 정의했다.

public static void solution() {
    for (int i = 0; i < C; i++) {
        fishing(i);
        move();
    }
}

 

fishing 함수는 문제 설명 그대로 구현하면 되므로 넘어가고

move 함수는 상어가 속도만큼 이동할 때 벽에 부딪힐 경우, 이동했던 카운팅을 2만큼 줄이면서 반대 방향으로 바꿔준다. 그 후 최종 이동한 위치에 이미 이동을 완료한 상어가 존재할 경우, 상어의 크기를 비교해 해당 칸을 차지해 주면 된다.

public static void move() {
    int[][] tmp = new int[R][C];

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (arr[i][j] > 0) {
                moveShark(tmp, i, j);
            }
        }
    }

    arr = tmp;
}

public static void moveShark(int[][] tmp, int i, int j) {
    int idx = arr[i][j];
    Tuple tuple = map.get(idx);

    for (int s = 0; s < tuple.s; s++) {
        i += directionX[tuple.d];
        j += directionY[tuple.d];

        if (i < 0 || j < 0 || i >= R || j >= C) {
            s -= 2;
            if (i < 0) tuple.d = 2;
            else if (i >= R) tuple.d = 1;
            else if (j < 0) tuple.d = 3;
            else if (j >= C) tuple.d = 4;
        }
    }

    if (tmp[i][j] > 0) {
        Tuple diffTuple = map.get(tmp[i][j]);

        if (diffTuple.z > tuple.z) {
            map.remove(idx);
        }
        else {
            map.remove(tmp[i][j]);
            tmp[i][j] = idx;
            map.put(idx, tuple);
        }
    }
    else {
        tmp[i][j] = idx;
        map.put(idx, tuple);
    }
}

---

3. 자바 풀이

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B17143.java

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

class Main {
    static int R, C;
    static int[][] arr;
    static Map<Integer, Tuple> map;
    static int[] directionX = {0, -1, 1, 0, 0};
    static int[] directionY = {0, 0, 0, 1, -1};
    static int result;

    public static void main(String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        for (int i = 0; i < C; i++) {
            fishing(i);
            move();
        }
    }

    public static void move() {
        int[][] tmp = new int[R][C];

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (arr[i][j] > 0) {
                    moveShark(tmp, i, j);
                }
            }
        }

        arr = tmp;
    }

    public static void moveShark(int[][] tmp, int i, int j) {
        int idx = arr[i][j];
        Tuple tuple = map.get(idx);

        for (int s = 0; s < tuple.s; s++) {
            i += directionX[tuple.d];
            j += directionY[tuple.d];

            if (i < 0 || j < 0 || i >= R || j >= C) {
                s -= 2;
                if (i < 0) tuple.d = 2;
                else if (i >= R) tuple.d = 1;
                else if (j < 0) tuple.d = 3;
                else if (j >= C) tuple.d = 4;
            }
        }

        if (tmp[i][j] > 0) {
            Tuple diffTuple = map.get(tmp[i][j]);

            if (diffTuple.z > tuple.z) {
                map.remove(idx);
            }
            else {
                map.remove(tmp[i][j]);
                tmp[i][j] = idx;
                map.put(idx, tuple);
            }
        }
        else {
            tmp[i][j] = idx;
            map.put(idx, tuple);
        }
    }

    public static void fishing(int j) {
        for (int i = 0; i < R; i++) {
            if (arr[i][j] > 0) {
                result += map.get(arr[i][j]).z;
                map.remove(arr[i][j]);
                arr[i][j] = 0;
                break;
            }
        }
    }

    public static class Tuple implements Comparable<Tuple> {
        int s;
        int d;
        int z;

        public Tuple (int s, int d, int z) {
            this.s = s;
            this.d = d;
            this.z = z; // 1위 2아래 3오 4왼
        }

        @Override
        public int compareTo(Tuple t) {
            return t.z - this.z;
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() 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());
        int M = Integer.parseInt(st.nextToken());

        arr = new int[R][C];
        map = new HashMap<>();

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());

            arr[r][c] = i;
            map.put(i, new Tuple(s, d, z));
        }

        br.close();
    }
}

---

4. 결과 및 회고

처음엔 상어 이동을 for문이 아닌 BFS를 이용해 이동시켰더니 시간초과가 났다. 역시 인덱스 접근이 빠른가보다