[백준]17143번 낚시왕

• 각 칸에는 상어가 최대 한 마리 들어있을 수 있다.
• 상어는 크기와 속도를 갖고 있다.
• 낚시 보드는
  • 1행~r행
  • 1열~c열
• 낚시왕의 시작과 끝
  • 0행 0열
  • 0행 c를 넘는 순간 끝
• 1초 동안 일어나는 일
  • 낚시왕이 오른쪽으로 한 column 이동한다.
  • 낚시왕이 있는 column에 있는 상어 중, 땅(0행)에 [ 가장 가까운 상어 ] 를 잡는다.
  • 상어를 잡으면, 격자판에서, 그 상어는 사라진다.
  • 상어가 이동한다.
• 상어의 이동
  • 주어진 속도로 이동 : ( 칸/ 초 )
  • 이동하려는 칸이, 경계를 넘는 경우 : curr < 1 || curc<1 || curr>r || curc>c
    • 방향을 반대로 바꿔!
    • 속력을 유지한채로 이동
• 이동을 마친 후 한 칸에, 상어는 두 마리 이상 있을 수 있다
  • 이 때, 크기가 큰 상어가 , 나머지 상어를 모두 잡아 먹는다.
• 구할 것 : 낚시왕이 잡은 상어크기와 합을 구하기

주어지는 것

• r , c
• s : 속력
• d: 방향
  • 1 : 위
  • 2 : 아래
  • 3 : 오른쪽
  • 4 : 왼쪽
• z : 크기

문제 풀이

board → 3차원 [r][c][3]

• 상어의
  • 크기
  • 속도
  • 방향

---

visit → 2차원 [r][c] boolean

• 낚시왕이 이동할 때 마다 false로 초기화

---

상어의 속력?

• 어차피 왕은 1초당 1칸씩 옆으로 이동한다.
• 즉, 칸/sec 로 주어지는 상어의 속력은
  • 한 번에 몇 칸 이동할것인가에 대한 정보

---

• 왕은 오른쪽으로 한칸씩 이동한다.
  • 해당 column에서 상어를 잡는다.
  • 매 번 visit함수를 초기화 시킨다.

---

• 상어를 잡는다 : 해당 column 을 0 부터 탐색 → 첫번째 상어를 잡는다

---

• 전체 board를 탐색하며, board[r][c][0]이 0이 아닌 곳을 만나면, 상어 이동함수를 호출 한다 .
  • 이동함수를 호출하며, 원래 자리 → 0 으로 세팅한다.

---

• 상어 이동 함수
  • 이동시키는 상어가 있던 자리는 0으로 세팅한다.
  • 따라서, 이 이동시키는 상어의 정보를 변수로 저장해두는게 필요할 수 있다. 아니면 꼬일 수도 있음...

---

• 한 마리의 상어 이동 후 처리
  • 이동한 위치에 다른 상어가 이미 존재?

    아직 이동하지 않은 상어(visit에서 false)라면, 해당 상어에 대한, 상어이동함수를 호출한다.

    • 해당 장리에는, 이동을 마친 상어를 위치시킨다.
    • board에 → 해당 상어 정보를 세팅
    • visit → true로 세팅한다.

    이동을 마친 상어라면 ( visit에서 true) → 두 상어의 크기를 비교 → 더 큰 상어를 남긴다.

  • 이동한 위치에 다른 상어가 존재 x

    board에 → 해당 상어 정보를 세팅

    visit → true로 세팅

---

package coding;
import java.io.*;
import java.util.*;

public class Main{
    /**
     * king 은 0,0에 위치
     * 상어들은 (1,1) 부터 (r,c)중에 위치한다.
     * */
    public static int[][][] board = new int[101][101][3];
    public static boolean[][] visit = new boolean[101][101];
    public static int gc,gr;

    public static int king = 0;  // 왕이 있는 열의 위치
    public static int sum = 0;

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;

    public static void setting() throws IOException {
        st = new StringTokenizer(br.readLine());
        gr = Integer.parseInt(st.nextToken());
        gc = Integer.parseInt(st.nextToken());
        int shark = Integer.parseInt(st.nextToken());
        int lr, lc, ls, ld, lz;
        for (int i = 0; i < shark; i++) {
            st = new StringTokenizer(br.readLine());
            lr = Integer.parseInt(st.nextToken());
            lc = Integer.parseInt(st.nextToken());
            ls = Integer.parseInt(st.nextToken());
            // 방향 : 위(0), 아래(1) 오른쪽(2), 왼쪽(3)
            ld = Integer.parseInt(st.nextToken()) - 1;
            lz = Integer.parseInt(st.nextToken());
            board[lr][lc][0] = lz;
            board[lr][lc][1] = ls;
            board[lr][lc][2] = ld;
        }
    }
    public static void solve(){
        for(king=1;king<=gc;king++){
            // init visit
            for(int r=1;r<=gr;r++) Arrays.fill(visit[r],false);
//            System.out.println("================"+king+"번째 열================");
            catchShark(king);

        }

    }
    /**
     * 왕이 column c에 있을 때 잡은 상어
     * -> 0에 가장 가까운 row의 상어를 잡는다 -> board 를 0으로 세팅
     * */
    public static void catchShark(int c){
        for(int r = 1 ; r <= gr; r++){
            if(board[r][c][0] != 0){
//                System.out.println("CATCH at ("+r+","+c+")");
                sum += board[r][c][0];
                board[r][c][0] = 0;
//                printShark();
                break;
            }
        }
        // 상어의 이동을 위한 상어들 탐색 -> O(100x100x100)
        for(int cr=1;cr <= gr;cr++){
            for(int cc=1;cc <= gc;cc++){
                if(board[cr][cc][0] != 0 && visit[cr][cc] == false){
                    shark_move(cr,cc);
                }
            }
        }
//        System.out.println("AFTER 1 SEC");
//        printShark();
    }
    public static void printShark(){
        for(int cr=1;cr <= gr;cr++){
            for(int cc=1;cc <= gc;cc++){
                System.out.printf("%5d  ",board[cr][cc][0]);
            }
            System.out.println();
        }
    }
    // 현재 (r,c)에 위치하는 상어를 움직이기
    public static void shark_move(int r, int c){
        int size = board[r][c][0], move = board[r][c][1],dir = board[r][c][2];
        int nr =r ,nc = c, idx = 0;
        board[r][c][0] = 0;
        visit[r][c] = true;
        int[] args = new int[2];
        // 상어 움직이기 -> 규칙을 찾는게 필요해보임
				// 각각에 대한 함수를 따로 선언함
        switch(board[r][c][2]){
            case 0:
                up(r,c,args);
                nr = args[0];
                dir = args[1];
                break;
            case 1:
                down(r,c,args);
                nr = args[0];
                dir = args[1];
                break;
            case 2:
                right(r,c,args);
                nc = args[0];
                dir = args[1];
                break;
            case 3:
                left(r,c,args);
                nc = args[0];
                dir = args[1];
                break;
        }
//        System.out.println("SHARK MOVE ("+r+","+c+") --> ("+nr+","+nc+")");
        afterSharkMove(nr,nc,size,move,dir);
    }

    /**
     * args : 이동 후 상어의 위치 . 이동한 상어의 정보 ( 크기, 속도, 방향 )
     * */
    public static void afterSharkMove(int r, int c, int size, int move, int dir){
        int pre = 0;
        // 다른 상어가 존재 : board[r][c][0]이 0이 아닌 경우 ->
				// while문을 한 것은 ,이전에 r,c에 위치하던 상어가 있었다면 이 상어를 이동시키고
				// 이동시킨 후에도, 그 상어가 r,c에 위치하는 경우도 있을 수 있기 때문
        while((pre=board[r][c][0]) != 0 ){
            if(visit[r][c]){
                // 다른 상어가 존재 && 이미 이동을 마친 상어
                if( pre < size){
                    putShark(r,c,size,move,dir);
                }
                break;
            }
            // 아직 이 상어가 이동을 한 적 없다면 -> 이 상어는 이동시킨다.
            else{
                shark_move(r,c);
            }
        }
        // 다른 상어가 존재 하지 않는 경우
        if(pre == 0) {
//            System.out.println("Main.afterSharkMove - when there's no other shark here.."+"r = " + r + ", c = " + c );
            putShark(r, c, size, move, dir);
        }
//        System.out.println("Main.afterSharkMove");
//        System.out.println("r = " + r + ", c = " + c + ", size = " + size + ", move = " + move + ", dir = " + dir);
//        printShark();
    }
    public static void putShark(int r, int c,int size, int move, int dir){
        visit[r][c] = true;
        board[r][c][0] = size;
        board[r][c][1] = move;
        board[r][c][2] = dir;
    }
    public static void main(String[] args) throws IOException{
        setting();
        solve();
        System.out.println(sum);
    }
    // right
    // mod 를 사용하려다보니 필요한 과정이 생겼다.
    public static void right(int r, int c, int[] args){
        int cnt = board[r][c][1]; // 이동해야하는 칸의 수
        // 이동 했을 때 방향
        int d =  (((c-1) + cnt)/(gc-1)) % 2; // 0 -> 방향 그대로 ( right )
        // 이동 후 칸 인덱스
        int idx = ((c-1) + cnt ) % (gc-1);
        if(d == 0 ){
            args[0] = idx+1;
            args[1] = 2;
        }else{
            args[0] = gc-idx;
            args[1] = 3;
        }
    }
    // left
    public static void left(int r, int c ,int[] args ){
        int lc = gc - c;
        int cnt = board[r][c][1]; // 이동해야하는 칸의 수
        // 이동 했을 때 방향
        int d =  ((lc + cnt)/(gc-1)) % 2; // 0 -> 방향 그대로 ( left )
        // 이동 후 칸 인덱스
        int idx = (lc + cnt ) % (gc-1);
        if(d ==0 ){
            // 0, 1 , 2 ,3,4,5
            args[0] = (gc-idx);
            args[1] = 3;
        }else{
            // 5 4 3 2 1 0
            args[0] = (idx+1);
            args[1] = 2;

        }
    }
    // left
    public static void up(int r, int c ,int[] args){
        int lr = gr - r;
        int cnt = board[r][c][1]; // 이동해야하는 칸의 수
        // 이동 했을 때 방향
        int d =  ((lr + cnt)/(gr-1)) % 2; // 0 -> 방향 그대로 (up )
        // 이동 후 칸 인덱스
        int idx = (lr + cnt ) % (gr-1);
        if(d == 0 ){
            // 0, 1 , 2 ,3,4,5
            args[0]= (gr-idx);
            args[1] = 0;

        }else{
            // 5 4 3 2 1 0
            args[0]= (idx+1);
            args[1] = 1;
        }
    }
    public static void down(int r, int c,int[] args){
        int cnt = board[r][c][1]; // 이동해야하는 칸의 수
        // 이동 했을 때 방향
        int d =  (((r-1) + cnt)/(gr-1)) % 2; // 0 -> 방향 그대로 (down )
        // 이동 후 칸 인덱스
        int idx = ((r-1) + cnt ) % (gr-1);

        if(d ==0 ){
            // 0, 1 , 2 ,3,4,5
            args[0]= idx+1;
            args[1] = 1;
        }else{
            // 5 4 3 2 1 0
            args[0]= gr-(idx);
            args[1]=0;
        }
    }
}