[BOJ - JAVA] (삼성전자 기출)17143 - 낚시왕 (구현, 시뮬레이션, BFS)

# 주소

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

17143번: 낚시왕

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Fishing{
    int x;
    int y;
    int speed;
    int direction;
    int size;
    Fishing(int x, int y, int speed, int direction, int size){
        this.x = x;
        this.y = y;
        this.speed = speed;
        this.direction = direction;
        this.size = size;
    }
}
class GG{
    static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int answer = 0;
        int n = scan.nextInt();
        int m = scan.nextInt();
        int k = scan.nextInt();
        List<Fishing>[][] arr = new List[n + 1][m + 1];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                arr[i][j] = new ArrayList<>();
        ArrayList<Fishing> list = new ArrayList<>();
        for(int i = 0; i < k; i++) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            int speed = scan.nextInt();
            int direction = scan.nextInt();
            int size = scan.nextInt();
            arr[a][b].add(new Fishing(a, b, speed, direction - 1, size));
            list.add(new Fishing(a, b, speed, direction - 1, size));
        }
        for(int i = 1; i <= m; i++){
            Fishing now = null;
            for(int j = 1; j <= n; j++){
                if(arr[j][i].size() == 1){
                    now = arr[j][i].get(0);
                    break;
                }
            }
            if(now != null){
                answer += now.size;
                arr[now.x][now.y].remove(0);
                int size = list.size();
                for(int j = 0; j < size; j++){
                    if(list.get(j).size == now.size){
                        list.remove(j);
                        break;
                    }
                }
            }
            int size = list.size();
            for(int j = 0; j < size; j++){
                Fishing temp = list.get(j);
                int nx = temp.x;
                int ny = temp.y;
                int speed = temp.speed;
                int direction = temp.direction;
                if(direction == 0 || direction == 1)
                    speed = speed % (2 * (n - 1));
                else
                    speed = speed % (2 * (m - 1));
                while (speed-- > 0){
                    nx += dir[direction][0];
                    ny += dir[direction][1];
                    if(nx <= 0 || ny <= 0 || nx >= n + 1 || ny >= m + 1){
                        nx -= dir[direction][0];
                        ny -= dir[direction][1];
                        if(direction == 0)
                            direction = 1;
                        else if(direction == 1)
                            direction = 0;
                        else if(direction == 2)
                            direction = 3;
                        else
                            direction = 2;
                        nx += dir[direction][0];
                        ny += dir[direction][1];
                    }
                }
                arr[temp.x][temp.y].remove(0);
                temp.x = nx;
                temp.y = ny;
                temp.direction = direction;
                arr[nx][ny].add(temp);
            }
            list = new ArrayList<>();
            for(int j = 1; j <= n; j++){
                for(int z = 1; z <= m; z++){
                    if(arr[j][z].size() > 1){
                        Collections.sort(arr[j][z], new Comparator<Fishing>() {
                            @Override
                            public int compare(Fishing o1, Fishing o2) {
                                return o2.size - o1.size;
                            }
                        });
                        arr[j][z] = new ArrayList<>(arr[j][z].subList(0, 1));
                        list.add(arr[j][z].get(0));
                    }else if(arr[j][z].size() == 1)
                        list.add(arr[j][z].get(0));
                }
            }
        }
        System.out.println(answer);
    }
}

오랜만에 포스팅하게 되어 반갑습니다 :)

최근에 난이도 높은 문제를 많이 풀고 있는데 저번주부터 올리려고 하니 블로그가 먹통이여서 포스팅을 못했습니다 ㅠㅠ

따끈한 삼성 전자 기출 문제를 풀어 보며 다시 포스팅을 열심히 해보겠습니다.

문제를 천천히 읽어 봅시다.

 

# 문제 접근법

1. 주인공이 한 칸씩 움직이며 가장 가까운 상어를 낚시 후 배열에서 삭제

2. 이후 상어들이 각자의 속도와 방향을 가지고 제 각기 움직이며 같은 칸에 여러 상어 존재 가능

3. 여러 상어가 존재할 경우 크기가 가장 큰 상어가 살아남음

4. 이 때 주인공은 오른쪽으로 한 칸씩 이동하여 사냥을 하는데, m번 행 이후에 도착할 때의 잡은 상어의 크기의 합을 구하기

 

이렇게 접근을 하시면 되겠습니다.

1을 구현하기 위해 2차원 배열을 사용해야 하고 2는 list에 담아야 함을 알 수 있습니다.

3에서는 각 칸에 여러 상어가 존재해야 하므로 클래스를 오버라이딩 하여 ArrayList를 배열로 사용해야 합니다. 

코드를 보며 확인해봅시다.

import java.util.*;
class Fishing{
    int x;
    int y;
    int speed;
    int direction;
    int size;
    Fishing(int x, int y, int speed, int direction, int size){
        this.x = x;
        this.y = y;
        this.speed = speed;
        this.direction = direction;
        this.size = size;
    }
}

Fishing클래스에 5가지의 매개 변수 전체를 사용할 것입니다.

다음과 같이 만들어 줍시다. speed는 속력, direction은 방향, size는 크기입니다.

 

 

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

방향 벡터는  정적 변수로 사용했습니다. 

저는 습관적으로 이렇게 사용하는데 다시 일일히 생성하는 것보다 항상 사용하는 것들은 static으로 선언하는 것이 좋습니다.

 

입력문을 보겠습니다.

 

Scanner scan = new Scanner(System.in);
int answer = 0;
int n = scan.nextInt();
int m = scan.nextInt();
int k = scan.nextInt();

n과 m, 그리고 상어의 수 k를 각각 Scanner로 입력 받습니다.

List<Fishing>[][] arr = new List[n + 1][m + 1];
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        arr[i][j] = new ArrayList<>();

이후 List타입의 Fishing을 제네릭에 담은 arr라는배열을 (n+1) x (m+1)크기로 선언합니다.

arr는 각 인덱스에 대해 List 성질을 가졌습니다.

따라서 2번째 줄부터 2중 for문을 이용하여 arr의 각 인덱스를 ArrayList로 선언합니다.

 

ArrayList<Fishing> list = new ArrayList<>();

arr도 있는데 이걸 굳이 왜 선언해야 할까 싶겠지만 이 list는 arr와는 다르게 모든 상어를 저장해서 관리합니다.

arr로 관리 가능한 것은 각 배열의 인덱스에 저장된 상어만 관리 가능한데요.

이 상어가 이동을 하면서 다른 배열로 이동했을 때 분명 저희가 for문을 사용하여 상어의 움직임을 관리할 것이기 때문에 중복해서 상어를 이동시킬 가능성이 존재합니다.

무슨 말이냐면, list라는 자료구조를 통해 각각의 상어를 관리해주어야지, arr를 통해 모든 상어를 관리하다보면 인덱스 별로 관리하기 때문에 다른 곳으로 앞에서 탐색한 상어가 뒤로 이동하여 다시 탐색되어 또 이동하는... 그런 번거로운 일이 발생할 수 있겠죠????

그래서 list로 따로 관리해주는 것입니다.

이해가 안되시면 조금 더 코드를 보면 와닿을 겁니다.

아직 입력문 끝나지 않았습니다.

for(int i = 0; i < k; i++) {
    int a = scan.nextInt();
    int b = scan.nextInt();
    int speed = scan.nextInt();
    int direction = scan.nextInt();
    int size = scan.nextInt();
    arr[a][b].add(new Fishing(a, b, speed, direction - 1, size));
    list.add(new Fishing(a, b, speed, direction - 1, size));
}

a, b, speed, direction, size를 입력 받아 arr[a][b]와 list에 각각 저장해줍시다.

여기까지가 입력문입니다.

이제부터 본격적으로 상어를 시뮬레이션 해보겠습니다.

 

 

for(int i = 1; i <= m; i++){
    Fishing now = null;
    for(int j = 1; j <= n; j++){
        if(arr[j][i].size() == 1){
            now = arr[j][i].get(0);
            break;
        }
    }

각각의 주인공은 총 1부터 m까지 이동하는 것을 연산해야 합니다.

그러므로 for문으로 가까운 상어를 찾을텐데요.

2번째 for문에서와 같이 arr[j][i]에 담긴 상어가 1마리 있다면 now에 상어를 담고 break해줍니다.

arr를 제가 배열로서 사용하고 있지만 이 arr배열의 각 인덱스들은 arrayList입니다.

그러므로 객체가 저장될 때 하나의 Fishing클래스가 객체가 되어 저장됩니다.

따라서 이 내부를 보기 위해서는 now에 접근연산자인 .을 찍어 size, speed 등을 알아낼 수 있습니다.

if(now != null){
    answer += now.size;
    arr[now.x][now.y].remove(0);
    int size = list.size();
    for(int j = 0; j < size; j++){
        if(list.get(j).size == now.size){
            list.remove(j);
            break;
        }
    }
}

만약 가져온 now가 있다면 answer에 now의 크기를 더해주고 arr에 해당 상어를 지웁니다.

왜 무조건 0인덱스만 지워지냐면, 상어가 여러 마리 겹치게 입력되지 않으며 이동을 통해 겹쳐질 경우 나중에 모두 제거할 것이기 때문입니다.

arr에서도 지웠으니 list에서도 마찬가지로 now의 size와 같은 객체를 list에서 remove합시다.

입력값을 잘 보시면 크기가 같은 상어는 주어지지 않으므로 위의 연산은 무리 없이 잘 동작합니다.

int size = list.size();
for(int j = 0; j < size; j++){
    Fishing temp = list.get(j);
    int nx = temp.x;
    int ny = temp.y;
    int speed = temp.speed;
    int direction = temp.direction;

이후 size번 동안 list를 loop합니다.

temp에는 list의 j번째 인덱스를 담아옵니다.

그리고 nx, ny, speed, direction을 temp에서 꺼내옵니다.

if(direction == 0 || direction == 1)
    speed = speed % (2 * (n - 1));
else
    speed = speed % (2 * (m - 1));

이 로직이 가장 가장 중요한 부분입니다.

이렇게 안짜시면 백프로 시간초과 뜨십니다. (제가 그랬읍니다)

이게 무슨 의미냐면... direction이 0이거나 1이란 것은 위, 아래로 움직이는 상어를 뜻하는데 이 때에는 (n -  1)에 2를 곱한것을 speed에서 나눈 나머지가 speed가 됩니다.

반대일 땐 m - 1을 대신 곱한게 되는데요.

자 왜그런지 봅시다.

문제의 입력 조건을 잘 보시면 speed가 10000까지나 됩니다. 이걸 일일히 한칸씩 움직여가다보면 상어가 수십 마리 존재하기 때문에 m값이 커질수록 굉장한 시간 낭비가 됩니다.

그러지 말고, 어짜피 상어가 움직이는 공간은 direction이 0 또는 1일 때 각각 위,아래로만 가능한데 이 것이 n이 5라면 위 아래 합쳐서 8칸만큼씩은 반복되는, 쓸데없는 움직임이라는 것이죠.

굳이 speed가 1000이고 n이 5일 때나, speed가 10000이고 n이 5일 때에나 각각 125번, 1250번 왕복하는 것은 똑같기 때문에 이 외에 추가로 더해진 나머지 값이 중요하단 것이지요.

제 글을 천천히 읽어보시면 아? 하시는게 있으실 겁니다. (이해 안되시면 문의해주세요)

따라서 speed를 direction에 따라 각각 나누어서 연산을 미리 해주시고 상어를 움직이는 것이 핵심입니다.

(첨에 시간초과 떠서 문제만 뚫어져라 쳐다봤는데 갑자기 보여서 저도 깜놀했씁니다. 다른 분은 어떻게 짜셨는지 저도모르는...)

이 이후도 중요합니다. 상어를 움직여봅시다.

 

while (speed-- > 0){
    nx += dir[direction][0];
    ny += dir[direction][1];
    if(nx <= 0 || ny <= 0 || nx >= n + 1 || ny >= m + 1){
        nx -= dir[direction][0];
        ny -= dir[direction][1];
        if(direction == 0)
            direction = 1;
        else if(direction == 1)
            direction = 0;
        else if(direction == 2)
            direction = 3;
        else
            direction = 2;
        nx += dir[direction][0];
        ny += dir[direction][1];
    }
}

nx와 ny를 제일 위에 정적 변수로 선언했던 dir배열에서 따와서 각각 이동합니다.

그래서 새롭게 구한 nx, ny가 0이 되거나 n +1 혹은 m + 1칸에 도달 했을 경우 배열의 밖에 있으므로 방금 더한 값을 빼고 direction의 방향을 정 반대로 바꾸어줍니다.

이 때 direction이 0이면 1, 1이면 0, 2이면 3, 3이면 2로 바꾼 뒤 nx와 ny를 다시 이동시킵니다.

모든 이동이 끝나면

arr[temp.x][temp.y].remove(0);
temp.x = nx;
temp.y = ny;
temp.direction = direction;
arr[nx][ny].add(temp);

arr에서 기존의 temp.x, temp.y 위치의 상어를 삭제합니다.

그리고 temp의 x, temp의 y를 nx, ny라고 바꾸고 방향도 최신화 하기 위해 direction으로 바꾼 뒤 arr[nx][ny]에 새로운 temp를 삽입합니다.

여기 까지가 상어의 이동입니다. 이제 겹치는 부분을 제거해보겠습니다.

list = new ArrayList<>();
for(int j = 1; j <= n; j++){
    for(int z = 1; z <= m; z++){
        if(arr[j][z].size() > 1){
            Collections.sort(arr[j][z], new Comparator<Fishing>() {
                @Override
                public int compare(Fishing o1, Fishing o2) {
                    return o2.size - o1.size;
                }
            });
            arr[j][z] = new ArrayList<>(arr[j][z].subList(0, 1));
            list.add(arr[j][z].get(0));
        }else if(arr[j][z].size() == 1)
            list.add(arr[j][z].get(0));
    }
}

list를 제일 먼저 초기화합니다. 각 위치에 한 마리씩 있는 상어를 구하기 위함입니다.

따라서 각 인덱스를 돌며 arr[j][z]가 1인 곳은 그냥 list에 상어를 그대로 삽입하시고 2이상인 곳만 따로 정렬을 하여 삽입합니다.

정렬은 다음과 같이 진행해줍니다.

Collections.sort(arr[j][z], new Comparator<Fishing>() {
    @Override
    public int compare(Fishing o1, Fishing o2) {
        return o2.size - o1.size;
    }
});

arr[j][z]는 arraylist타입이기 때문에 이 list형태의 자료구조를 Collctions 라이브러리를 통해 정렬할 수 있습니다.

Comparator라는 인터페이스를 통해 정렬해볼 텐데, 람다식으로도 가능하지만 좀 더 세세하게 보여드리기 위해 다음과 같이 작성했습니다.

Comprator인터페이스는 compare라는 메서드를 내장하고 있습니다.

o1이라는 객체와 o2라는 객체를 각각 비교하는데, o2.size - o1.size 이렇게 입력하시면 o2.size - o1.size가 양수가 되게 정렬할 수 있습니다.

즉, o2의 size가 o1의 size보다 더 크게 정렬할 수 있다는 뜻이므로 이는 내림차순을 의미합니다.

반대로 o1.size - o2.size 이렇게 작성하시면 오름차순으로 정렬할 수 있습니다.

arr[j][z] = new ArrayList<>(arr[j][z].subList(0, 1));
list.add(arr[j][z].get(0));

이후 정렬된 arr[j][z]를 0부터 1까지 subList메서드를 이용하여 list를 잘라서 저장합니다.

마지막으로 list에 다시 arr[j][z]의 0번째 객체를 저장하여 로직을 마칩니다.

그럼 정답을 확인해보시면 정답이 될 거에요. (안되면 문의 꼭)

 

이 문제는 삼성전자 SW 기출 문제입니다. 골드 2수준 답게 상당히 시간이 걸렸습니다.

상어 이동 짜는데 30분, list 자르는 부분에서 이해할 수 없는 오류가 터져서 3시간... 또 이후 시간 초과 떠서 speed 부분 간소화 로직 짜는데 10분.. 코드 리팩토링 30분... 엄청 걸렸네요.

실제 시험장에서 제대로 풀 수 있을진 모르겠지만 어쨌든 어떤 코드도 참고 안하고 혼자해결해서 뿌듯합니다.

근데 삼성 전자 기출 문제들은 다 골드난이도인데 실제 체감은 그 이상인 것 같은건 기분...탓인가요? ㅠㅠ