[백준]JAVA - 17143번: 청소왕

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

17143번: 낚시왕

풀이

위 문제의 로직은 아래와 같다.

 

1. 낚시왕이 한 칸 오른쪽으로 이동한다.
2. 해당 열에 해당하는 가장 가까운 상어를 잡는다.
3. 살아있는 상어들은 이동한다.

 

1. 낚시왕이 한 칸 오른쪽으로 이동한다.

for (int i=1; i<=C; i++) {
    MovePerson(i); // 이동한 열에서 가장 가까운 상어 잡기.
    MoveShark();   // 상어 이동.
}

열의 개수만큼 반복문을 돌려서 2번, 3번 로직을 수행한다.

 

2. 해당 열에 해당하는 가장 가까운 상어를 잡는다.

for (int row=1; row<=R; row++) {
    if (map[row][col] != null) { // 상어가 있는 경우
        ans += map[row][col].size;
                
        map[row][col] = null;
        break;
    }
}

행의 개수만큼 반복문을 돌려서 가장 가까운 상어를 잡고, 배열에서 삭제시킨다. 위 과정까지는 큰 어려움 없이 해결할 수 있을 것이라고 생각된다.

 

3. 살아있는 상어들은 이동한다.

3번 로직에서 주의할 점은 두 가지가 있다.

  1) 상어들이 이동하는 과정

  2) 배열의 복사

public static void MoveShark() {
    Shark[][] copyMap = new Shark[R+1][C+1];
        
    for (int row=1; row<=R; row++) {
        for (int col=1; col<=C; col++) {
            if (map[row][col] != null) {
                Shark shark = map[row][col];
                    
                int nx = shark.x;
                int ny = shark.y;
                int d = shark.dir;
                int speed = shark.sec;
                if(d == 0 || d == 1) speed %= (R - 1) * 2;
                else speed %= (C - 1) * 2;
                    
                for (int i=0; i<speed; i++) {
                    if (nx == 1 && d == 0) d = 1;
                    else if (nx == R && d == 1) d = 0;
                    else if (ny == C && d == 2) d = 3;
                    else if (ny == 1 && d == 3) d = 2;
                        
                    nx += dx[d];
                    ny += dy[d];
                }
                    
                if (copyMap[nx][ny] != null && copyMap[nx][ny].size > shark.size) continue;
                    
                copyMap[nx][ny] = new Shark(nx, ny, shark.sec, d, shark.size);
            }
        }
    }
        
    map = copyMap;
}

1) 상어들이 이동하는 과정

위 문제는 상어가 맵을 벗어난 경우, 정반대의 방향으로 남은 거리만큼 이동한다. 예를 들어, (0, 2) 에 있는 상어가 왼쪽으로 5칸만큼 이동한 다고 하면 (0,1) (0,0), (0,1) (0,2)가 된다.

 

상어를 반복문으로 한 칸씩 이동시키면 시간 초과가 발생한다. 시간 초과 에러를 발생시키지 않으려면 점화식을 발견해야한다. 점화식은 다음과 같다.

if(d == 0 || d == 1) speed %= (R - 1) * 2;
else speed %= (C - 1) * 2;

한 번에 움직이는 거리 %= (열의 크기 or 행의 크기 - 1) * 2 를 하게 되면 벽면을 찍고 제자리로 돌아온다. 여기서 발생한 나머지값만큼만 반복문을 통해서 이 동시 켜주면 된다. 위 과정을 해주는 이유는 한 마리의 상어가 양쪽의 벽을 한 번씩 찍고 제자리로 돌아오는 것은 시간을 없애주기 위함이다.

 

2) 배열의 복사

상어가 동시에 이동한다. 하지만 프로그램에서는 동시에 이동시킬 수 없다. 그렇다고 Map 배열을 이용해서 한 마리씩 이동시키면 "큰 상어는 작은 상어를 잡아먹는다." 조건에서 에러가 발생할 수 있다.

 

동시에 이동했을 경우에는 그 위치에 존재하지않지만 한 마리씩 이동했을 경우에는 그 위치에 상어가 존재할 수 있기 때문이다. 이 오류를 해결하기 위해선 copyMap을 사용해야 한다.

 

상어를 한 마리씩 이동시키면서 copyMap에 저장을 시킨다. copyMap에 들어간 건 이미 이동이 완료된 상어만 있기 때문에 이동한 위치에 상어가 이미 존재한다면 크기를 비교해서 잡아먹으면 된다.

// 이동을 마친 상어가 이미 존재하고, 그 상어의 크기가 더 클 경우
if (copyMap[nx][ny] != null && copyMap[nx][ny].size > shark.size) continue;

copyMap[nx][ny] = new Shark(nx, ny, shark.sec, d, shark.size);

 

<최종코드>

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

public class Main {
    static int R, C, M, ans = 0;
    static int[] dx = {-1, 1, 0, 0}; // 위 아래 오 왼
    static int[] dy = {0, 0, 1, -1};
    static Shark[][] map;
    
    public static class Shark {
        int x, y, sec, dir, size;
        
        public Shark (int x, int y, int sec, int dir, int size) {
            this.x = x;
            this.y = y;
            this.sec = sec;
            this.dir = dir;
            this.size = size;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        R = Integer.parseInt(st.nextToken()); // x
        C = Integer.parseInt(st.nextToken()); // y
        M = Integer.parseInt(st.nextToken()); // 상어 개수
        
        map = new Shark[R+1][C+1];
        
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            
            map[x][y] = new Shark(x, y, s, d-1, z);
        }
        
        // 오른쪽으로 한 칸씩 이동.
        for (int i=1; i<=C; i++) {
            MovePerson(i); // 이동한 열에서 가장 가까운 상어 잡기.
            MoveShark();   // 상어 이동.
        }
        
        System.out.println(ans);
    }
    
    public static void MovePerson (int col) {
        for (int row=1; row<=R; row++) {
            if (map[row][col] != null) {
                ans += map[row][col].size;
                
                map[row][col] = null;
                break;
            }
        }
    }
    
    public static void MoveShark() {
        Shark[][] copyMap = new Shark[R+1][C+1];
        
        for (int row=1; row<=R; row++) {
            for (int col=1; col<=C; col++) {
                if (map[row][col] != null) {
                    Shark shark = map[row][col];
                    
                    int nx = shark.x;
                    int ny = shark.y;
                    int d = shark.dir;
                    int speed = shark.sec;
                    if(d == 0 || d == 1) speed %= (R - 1) * 2;
                    else speed %= (C - 1) * 2;
                    
                    for (int i=0; i<speed; i++) {
                        if (nx == 1 && d == 0) d = 1;
                        else if (nx == R && d == 1) d = 0;
                        else if (ny == C && d == 2) d = 3;
                        else if (ny == 1 && d == 3) d = 2;
                        
                        nx += dx[d];
                        ny += dy[d];
                    }
                    
                    if (copyMap[nx][ny] != null && copyMap[nx][ny].size > shark.size) continue;
                    
                    copyMap[nx][ny] = new Shark(nx, ny, shark.sec, d, shark.size);
                }
            }
        }
        
        map = copyMap;
    }
}