[BOJ] 17143번. 낚시왕 - JAVA

문제 링크

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

17143번: 낚시왕

 

📝 풀이 과정

문제 유형 : 시뮬레이션 

 

느낀 점

처음에 혼자 풀고 난 뒤 채점 현황을 보니 내것보다 메모리는 10000KB 적고 시간은 거의 5배가 적게 걸리게 푸신 분을 보고 어떻게 다른가 코드를 보고 난 뒤 다시 풀어봤다. 그리고 나서 다시 제출하니 거의 다가 비슷한 코드였는데 메모리와 소요 시간이 줄긴 했지만 실행시간은 여전히 3배 차이가 났다. 

다시 한번 다른 점을 찾아보니 딱 한군데가 달랐는데 

 

int k = shark.d < 3 ? shark.dist % ((N-1) * 2) : shark.dist % ((M-1) * 2);

 

이 부분이었다.  위의 코드는 상어가 한 방향으로 가다가 부딪히고 다시 부딪혀서 원래 자리로 같은 방향과 함께 돌아왔을 때를 연산해준 것이었다. 이 코드 한 줄이 실행 시간을 3배나 차이나게 한다니 코드 최적화의 필요성을 다시 한번 느끼게 되었다.

 

설명

• Shark 클래스
  • dist, d, z : 상어의 속도 = 이동 거리, 이동 방향, 크기
• fishing(int fisher) 메소드
  • fisher 열에 낚시꾼이 위치했을 때, 땅과 가까운 상어를 잡는다고 했으니 0 번 행부터 상어가 있는지 탐색해 있다면 그 칸에 위치한 상어의 크기를 ans 변수에 더함
  • 그 칸에 위치한 상어는 null 로 변경
• move() 메소드
  • map 에 상어가 있다면 (null 이 아니라면) 상어를 이동
  • 상어가 이동할 거리 중 불필요한 부분은 % 연산으로 줄여줌
  • 상어가 이동하는데, 격자를 벗어나면 방향을 바꾸고 다시 이동
  • 이동한 위치에 다른 상어가 있는데, 그 상어보다 현재 이동할 상어가 더 큰 경우에만 newMap에 상어를 표시
  • 아니라면 아무런 표시 x (이동한 위치에는 원래 있던 상어가 위치함)
  • 아무 상어가 없다면 newMap 에 현재 이동한 상어를 표시
  • map에 newMap 을 복사

 

💻 코드

import java.io.*;
import java.util.*;
 
public class Main_bj_17143_낚시왕 {
    
    static int N, M, ans;
    static int[] dr = {0, -1, 1, 0, 0};
    static int[] dc = {0, 0, 0, 1, -1};
    static Shark[][] map;
    
    static class Shark{
        int dist, d, z;
 
        public Shark(int dist, int d, int z) {
            super();
            this.dist = dist;
            this.d = d;
            this.z = z;
        }
    }
 
    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/input_bj_17143.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        
        map = new Shark[N][M];
        
        for(int i=0; i<S; i++) {
            st = new StringTokenizer(br.readLine(),  " ");
            int r = Integer.parseInt(st.nextToken())-1;
            int c = Integer.parseInt(st.nextToken())-1;
            int dist = Integer.parseInt(st.nextToken());        // 속도 = 거리
            int d = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            
            map[r][c] = new Shark(dist, d, z);
        }
        
        ans = 0;
        for(int fisher = 0; fisher < M; fisher++) {
            // 1. 낚시
            fishing(fisher);
            
            // 2. 상어 이동
            move();
        }
        
        System.out.println(ans);
        br.close();
    }
    
    static void fishing(int fisher) {
        for(int i=0; i<N; i++) {
            if(map[i][fisher] != null) {
                ans += map[i][fisher].z;
                map[i][fisher] = null;
                return;
            }
        }
    }
    
    static void move() {
        Shark[][] newMap = new Shark[N][M];        // 이동한 자리 표시
        
        for(int i=0; i<N; i++) {
             for(int j=0; j<M; j++) {
                if(map[i][j] != null) {
                    
                    int r = i;
                    int c = j;
                    Shark shark = map[i][j];
                    
                    // 1과 2는 상하, 3과 4는 좌우 방향, 벽에 부딪혔다 되돌아왔을 때 거리
                    int k = shark.d < 3 ? shark.dist % ((N-1) * 2) : shark.dist % ((M-1) * 2);
                    
                    while(k-- > 0) {
                        r += dr[shark.d];
                        c += dc[shark.d];
                        
                        if(r<0 || r>=N || c<0 || c>=M) {
                            r -= dr[shark.d];
                            c -= dc[shark.d];            // 원상 복구
                            
                            shark.d = shark.d % 2 == 0 ? shark.d-1 : shark.d +1;    // 방향 바꿈
                            
                            r += dr[shark.d];            // 다시 이동
                            c += dc[shark.d];
                        }
                    }
                    
                    if(newMap[r][c] != null) {
                        if(shark.z > newMap[r][c].z) newMap[r][c] = shark;
                    } else {
                        newMap[r][c] = shark;
                    }
                    
                }
            }
        }
        
        map = newMap;
    }
 
}
 

 

📌 채점 결과

1. 혼자 풀었을 때 

2. 거의 비슷한 코드로 작성했을 때

3. 상어의 이동거리를 최적화시켰을 때