[BOJ/Java] 17143. 낚시왕

[BOJ/Java] 17143. 낚시왕

17143번: 낚시왕

---

문제 해석

이 문제에서는 R x C 크기의 격자에 상어가 배치되어 있으며, 낚시왕이 상어를 잡는 과정을 시뮬레이션한다. 낚시왕은 격자의 왼쪽 열부터 시작하여 매 턴마다 오른쪽으로 한 칸씩 이동한다. 각 칸에서 가장 가까운 상어를 잡은 후, 모든 상어가 자신의 규칙에 따라 이동한다. 이동 중 상어가 동일한 칸에 도착하면 크기가 가장 큰 상어만 살아남는다. 목표는 낚시왕이 잡은 상어의 크기 합을 최대로 하는 것이다.

풀이 과정

이 게임의 진행은 다음과 같다. 먼저, 낚시왕이 가장 가까운 상어를 잡는 catchShark 함수를 실행하고, 상어가 이동하는 move 메소드를 각 상어에 대해 호출한다. 이동 후, 같은 위치에 여러 상어가 있을 경우 크기가 가장 큰 상어만 남기는 checkShark 함수를 실행한다.

 

• sol 메소드는 각 열에 대해 상어를 잡고 상어의 이동을 처리하는 전체 과정을 총괄한다.
• setArray 메소드는 상어의 위치를 추적하기 위한 방문 배열을 초기화한다.
• Shark 클래스는 상어의 속성을 정의하고, 이동 로직을 포함한다. 이동 로직에서는 상어가 격자의 경계에 도달하면 방향을 바꿔 이동한다.

코드

package edu.ssafy.im.BOJ.Gold.G1.No17143;

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

public class Main {
    int R, C; // 격자의 행과 열
    List<Shark> sharkList; // 상어들을 저장할 리스트
    int ans = 0; // 낚시왕이 잡은 상어 크기의 합
    int[][] direction = {{0, 0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}}; // 상어 이동 방향 (정지, 상, 하, 우, 좌)
    int[][] visited; // 각 위치의 상어 인덱스를 기록하는 배열

    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken()); // 상어의 수

        sharkList = new ArrayList<>();
        setArray();
        int idx = 0;
        for (int i = 0; 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()); // 상어의 크기
            sharkList.add(new Shark(r, c, s, d, z));
            visited[r][c] = idx++; // 상어 위치 등록
        }

        sol(); // 시뮬레이션 시작
        bw.write(ans + "\n"); // 결과 출력
        bw.flush();
        bw.close();
    }

    private void sol() {
        for (int i = 0; i < C; i++) { // 모든 열에 대해 반복
            catchShark(i); // 상어 잡기
            setArray(); // 방문 배열 초기화
            for (Shark s : sharkList) { // 모든 상어 이동
                s.move();
            }
            checkShark(); // 상어 위치 겹침 처리
        }
    }

    private void setArray() {
        visited = new int[R][C]; // 방문 배열 초기화
        Arrays.fill(visited, -1); // 초기 값 -1로 설정
    }

    private void catchShark(int c) {
        for (int r = 0; r < R; r++) {
            if (visited[r][c] != -1) { // 상어 발견
                ans += sharkList.get(visited[r][c]).z; // 상어 크기 점수 추가
                sharkList.get(visited[r][c]).z = -1; // 상어 제거 표시
                return; // 한 마리 잡으면 종료
            }
        }
    }

    private void checkShark() {
        for (int i = 0; i < sharkList.size(); i++) {
            Shark s = sharkList.get(i);
            if (s.z == -1) continue; // 이미 잡힌 상어는 건너뛰기
            int idx = visited[s.r][s.c]; // 현재 위치의 상어
            if (idx == -1) { // 상어가 없다면
                visited[s.r][s.c] = i; // 상어 인덱스 등록
            } else if (s.z > sharkList.get(idx).z) { // 현재 상어가 더 크면
                sharkList.get(idx).z = -1; // 다른 상어 제거
                visited[s.r][s.c] = i; // 상어 인덱스 갱신
            } else { // 다른 상어가 더 크면
                s.z = -1; // 현재 상어 제거
            }
        }
    }

    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;
            // 이동 사이클 최적화: 주어진 경계를 넘어서지 않도록 이동 횟수 조정
            if (d == 1 || d == 2) {
                this.s %= 2 * (R - 1);
            } else if (d == 3 || d == 4) {
                this.s %= 2 * (C - 1);
            }
        }

        public void move() {
            for (int i = 0; i < this.s; i++) {
                int nextR = r + direction[d][0];
                int nextC = c + direction[d][1];
                if (nextR < 0 || nextR >= R || nextC < 0 || nextC >= C) { // 경계를 넘어서면 방향 전환
                    d = d == 1 ? 2 : d == 2 ? 1 : d == 3 ? 4 : 3;
                } else {
                    r = nextR;
                    c = nextC;
                }
            }
        }
    }
}

시간 복잡도 분석

이 시뮬레이션의 시간 복잡도는 O(MC)이다, 여기서 M은 상어의 수, C는 열의 수를 의미한다. 각 열마다 모든 상어를 이동시키고, 겹치는 상어를 확인하여 처리한다.

느낀점

이 문제를 통해 복잡한 시뮬레이션 문제를 처리하는 방법을 배웠다. 상어의 이동과 상호작용을 관리하는 것이 도전적이었으며, 효과적인 데이터 구조 사용이 중요함을 깨달았다. 이러한 경험은 앞으로 복잡한 시뮬레이션 및 최적화 문제에 대한 접근 방식을 개선하는 데 도움이 될 것이다.