[백준] G1 17143 낚시왕 (java)

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

17143번: 낚시왕

 

 

풀이

 

0) 상어의 인덱스를 담을 map_idx[][]와 상어의 크기를 담을 map_z[][]를 생성하고 입력값을 기반으로 초기화한다.

1) 입력받은 상어들을 List<Shark>에 담는다. Shark 클래스는 r, c, s, d, z, isDead로 이루어져 있다.
  1-1) 상어는 1번부터 존재한다. List의 인덱스를 상어의 번호로 저장하기 위해 죽은 상어를 List에 최초 한번 add 한다.

2) 낚시왕을 0번 부터 C 까지 한칸씩 오른쪽으로 이동한다.

3) 낚시왕의 열에 상어가 존재하면 가장 가까운 map_z[][] 값을 answer에 더한다. 해당상어의 isDead를 true로 변경한다.

4) 상어를 이동시킨다.
  4-1) List를 탐색하며 isDead가 false 인 상어만 이동시킨다.
  4-2) 이동할 상어의 원래 위치(r, c)를 저장하고 map_idx[r][c] 와 map_z[r][c] 를 0으로 초기화 한다.
  4-3) 상어의 이동은 1칸씩 d 방향으로 이동하며 만약 범위를 넘어가면 방향을 반대로 바꾼다.
  4-4) 모든 상어의 이동이 끝나고 List가 초기화 되면 상어들의 위치를 기반으로 map_idx[r][c]와 map_z[r][c]를 갱신한다.
  4-5) 이때, 해당 좌표에 이미 다른 상어가 존재한다면 큰놈을 살리고 작은놈의 isDead를 true로 바꾼다.

5) 이동이 끝난 상어 List를 기반으로 map_idx[r][c]와 map_z[r][c]를 초기화한다. 2)로 돌아간다.

 

 

주의사항

 

1) 작은 상어가 큰 상어에게 먹히는 로직은 모든 상어가 이동이 완료된 후 이루어져야 한다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BJ_G1_17143_낚시왕 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static List<Shark> list;
    static int R,C,M, map_idx[][], map_z[][];

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        tokens = new StringTokenizer(input.readLine());

        R = Integer.parseInt(tokens.nextToken());
        C = Integer.parseInt(tokens.nextToken());
        M = Integer.parseInt(tokens.nextToken());
        map_idx = new int [R][C];
        map_z = new int [R][C];
        list = new ArrayList<>();
        list.add(new Shark(0,0,0,0,0,true)); // 1번 부터 시작하기 위해 0번 상어를 임의로 넣음
        for(int i=1; i<M+1; i++){
            tokens = new StringTokenizer(input.readLine());
            int r = Integer.parseInt(tokens.nextToken())-1;
            int c = Integer.parseInt(tokens.nextToken())-1;
            int s = Integer.parseInt(tokens.nextToken());
            int d = Integer.parseInt(tokens.nextToken())-1;
            int z = Integer.parseInt(tokens.nextToken());

            map_idx[r][c] = i;
            map_z[r][c] = z;
            list.add(new Shark(r,c,s,d,z,false));
        }

        int answer = 0;

        for(int c=0; c<C; c++){
            for(int r=0; r<R; r++){
                if(map_idx[r][c] != 0){
                    answer += map_z[r][c];
                    list.get(map_idx[r][c]).isDead = true;
                    map_idx[r][c] = 0;
                    map_z[r][c] = 0;
                    break;
                }
            }
            moveShark();
        }
        System.out.println(answer);
    }

    private static void moveShark() {
        for(int i=1; i<M+1; i++){
            if(!list.get(i).isDead){
                map_idx[list.get(i).r][list.get(i).c] = 0;
                map_z[list.get(i).r][list.get(i).c] = 0;
                int nr = 0, nc = 0;
                for(int s=0; s<list.get(i).s; s++){
                    nr = list.get(i).r + dr[list.get(i).d];
                    nc = list.get(i).c + dc[list.get(i).d];
                    if(isIn(nr,nc)){
                        list.get(i).r = nr;
                        list.get(i).c = nc;
                    }else{
                        if(list.get(i).d == 0){
                            list.get(i).d = 1;
                        }else if(list.get(i).d == 1){
                            list.get(i).d = 0;
                        }else if(list.get(i).d == 2){
                            list.get(i).d = 3;
                        }else{
                            list.get(i).d = 2;
                        }
                        s--;
                    }
                }
            }
        }
        for(int i=1; i<M+1; i++){
            if(!list.get(i).isDead){
                if(map_z[list.get(i).r][list.get(i).c] < list.get(i).z){
                    list.get(map_idx[list.get(i).r][list.get(i).c]).isDead = true;
                    map_z[list.get(i).r][list.get(i).c] = list.get(i).z;
                    map_idx[list.get(i).r][list.get(i).c] = i;
                }else{
                    list.get(i).isDead = true;
                }
            }
        }
    }


    static boolean isIn(int r, int c){
        return (r>=0 && c>=0 && r<R && c<C);
    }

    static class Shark{
        int r;
        int c;
        int s;
        int d;
        int z;
        boolean isDead;

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

        @Override
        public String toString() {
            return "Shark{" +
                    "r=" + r +
                    ", c=" + c +
                    ", s=" + s +
                    ", d=" + d +
                    ", z=" + z +
                    ", isDead=" + isDead +
                    '}';
        }
    }

    static int dr[] = {-1,1,0,0};
    static int dc[] = {0,0,1,-1};


    static String src =
            "2 2 4\n" +
            "1 1 1 1 1\n" +
            "2 2 2 2 2\n" +
            "1 2 1 2 3\n" +
            "2 1 2 1 4";
}

 

 

 

후기

 

 생각보다 잘 안풀려서 골치아팠던 문제였다.

삼성 SW 역량 테스트 기출 문제라는데 확실히 삼성은 시뮬레이션을 좋아하는것 같다.

다 풀고 다른 풀이를 찾아보니 나와 시간이 많이 차이났다. 보아하니 나처럼 상어의 이동을 한칸씩 하지 않고 한번에 계산해서 이동시킨거같다. 생각을 못한것은 아닌데 계산하기 귀찮아서 안했다. 다시 풀기도 귀찮다.

또 방향전환도 별로 스마트하지 못했는데 if else로 케이스를 구분할 필요없이 계산만 잘하면 되더라.. 이것도 생각을 못한건 아닌데 귀찮아서 크게 고민하지 않았다.

팁을 하나 배웠다면 방향전환할때, 상하좌우의 순서를 어떻게 배치하냐에 따라서 계산이 깔끔해질 수 있다는것이다.

예를들어 이번 문제와 같이

상하좌우를 0 1 2 3 으로 둔다면 그 반대는 하상우좌 이다.
하상우좌는 1 0 3 2 가 된다.

0 1 2 3 에서 1 0 3 2 가 되려면? 난 모르겠다.

하지만
상좌하우를 0 1 2 3 으로 둔다면 그 반대는 하우상좌 이다.
하우상좌는 2 3 0 1 이 된다.

0 1 2 3 에서 2 3 0 1 이 되려면?  그냥 (d+2)%4 하면 그만이다.

이제 방향전환하는 문제를 만나면 조금 더 스마트하게 풀도록 노력하자.