[BOJ - JAVA] (삼성전자 기출) 19237 - 어른 상어 (구현, 시뮬레이션)

# 주소

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

19237번: 어른 상어

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Shark{
    int x;
    int y;
    int dir;
    int num;
    Shark(int x, int y, int dir, int num){
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.num = num;
    }
}
class Gas{
    int x;
    int y;
    int size;
    int num;
    Gas(int x, int y, int size, int num){
        this.x = x;
        this.y = y;
        this.size = size;
        this.num = num;
    }
}
class Sum{
    static int n, m, k;
    static List<Shark>[][] sharkList;
    static List<Shark> list;
    static List<Gas>[][] gasList;
    static List<Integer>[][] dirList;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        k = scan.nextInt();
        dirList = new List[m][4];//방향 저장
        sharkList = new List[n][n];//상어 위치를 배열에 저장
        list = new ArrayList<>();//상어 저장
        gasList = new List[n][n];//가스 위치를 배열에 저장
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                int x = scan.nextInt() - 1;
                sharkList[i][j] = new ArrayList<>();
                gasList[i][j] = new ArrayList<>();
                //sharkList와 gasList각 인덱스를 List로 선언함
                if(x >= 0) {
                    sharkList[i][j].add(new Shark(i, j, -1, x));
                    list.add(new Shark(i, j, -1, x));
                }
                //만약 x가 0보다 크-같으면 sharkList와 list에 각각 저장 
            }
        }
        Collections.sort(list, new Comparator<Shark>() {
            @Override
            public int compare(Shark o1, Shark o2) {
                return o1.num - o2.num;
            }
        });
        //상어 번호 별로 오름차순 정렬(바로 아래의 for문에서 list의 방향 넣기 위해)
        for(int i = 0; i < m; i++){
            int t = scan.nextInt() - 1;
            list.get(i).dir = t;
            sharkList[list.get(i).x][list.get(i).y].get(0).dir = t;
        }//list에 방향 삽입 및 sharkList에도 방향 삽입
        for(int i = 0; i < m; i++)
            for(int j = 0; j < 4; j++)
                dirList[i][j] = new ArrayList<>();
        //dirList는 m x 4의 크기를 가진 list 배열
        int count = 0;
        for(int i = 0; i < 4 * m; i++){
            ArrayList<Integer> temp = new ArrayList<>();
            for(int j = 0; j < 4; j++)
                temp.add(scan.nextInt() - 1);
            dirList[i / 4][count].addAll(temp);
            count++;
            if(count == 4)
                count = 0;
        }
        //dirList에 temp를 삽입함
        int answer = 0;
        while (answer++ <= 1000){
            int size = list.size();
            for(int i = 0; i < size; i++) {
                Shark now = list.get(i);
                if (gasList[now.x][now.y].size() == 1)
                    gasList[now.x][now.y].get(0).size = k;
                else if (gasList[now.x][now.y].size() == 0)
                    gasList[now.x][now.y].add(new Gas(now.x, now.y, k, now.num));
            }
            //size동안 가스값 조정(새로운 인덱스면 가스 추가, 기존 인덱스면 k로 변경)
            for(int i = 0; i < size; i++){
                Shark now = list.get(i);
                int nx = 0;
                int ny = 0;
                int d = 0;
                boolean isOk = false;
                ArrayList<Integer> temp = new ArrayList<>();
                for(int j = 0; j < 4; j++){
                    d = dirList[now.num][now.dir].get(j);
                    nx = now.x + dir[d][0];
                    ny = now.y + dir[d][1];
                    if(nx < 0 || ny < 0 || nx >= n || ny >= n)
                        continue;
                    if(gasList[nx][ny].size() == 0){
                        isOk = true;
                        break;
                    }
                    if(gasList[nx][ny].get(0).num == now.num){
                        temp.add(nx);
                        temp.add(ny);
                        temp.add(d);
                    }
                }
                //새로운 상어 위치 갱신. 만약 자신의 인덱스 방문한다면 일단 temp에 넣기
                if(isOk){
                    sharkList[now.x][now.y].remove(0);
                    sharkList[nx][ny].add(new Shark(nx, ny, d, now.num));
                    now.x = nx;
                    now.y = ny;
                    now.dir = d;
                    //가스가 없는 인덱스를 찾으면 nx, ny삽입
                }else{
                    sharkList[now.x][now.y].remove(0);
                    sharkList[temp.get(0)][temp.get(1)].add(new Shark(temp.get(0),temp.get(1),temp.get(2),now.num));
                    now.x = temp.get(0);
                    now.y = temp.get(1);
                    now.dir = temp.get(2);
                    //가스가 있는 인덱스만 있다면 우선순위에 따라 제일 먼저 넣은 temp이용
                }
            }
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(gasList[i][j].size() == 1){
                        gasList[i][j].get(0).size--;
                        if(gasList[i][j].get(0).size == 0)
                            gasList[i][j].remove(0);
                    }
                }
            }
            //모든 인덱스를 돌며 gas가 있는 인덱스는 size를 감소시키고 0이면 배열에서 제거 
            HashSet<Integer> hashSet = new HashSet<>();
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(sharkList[i][j].size() > 1){
                        Collections.sort(sharkList[i][j], new Comparator<Shark>() {
                            @Override
                            public int compare(Shark o1, Shark o2) {
                                return o1.num - o2.num;
                            }
                        });
                        for(int z = 1; z < sharkList[i][j].size(); z++)
                            hashSet.add(sharkList[i][j].get(z).num);
                        sharkList[i][j] = new ArrayList<>(sharkList[i][j].subList(0, 1));
                    }
                }
            }
            //n x n번 탐색하며 shark가 2이상인 지점을 찾아 상어 번호에 따라 오름차순 정렬 뒤 커팅
            ArrayList<Shark> z = new ArrayList<>();
            for(int i = 0; i < list.size(); i++)
                if(!hashSet.contains(list.get(i).num))
                    z.add(list.get(i));
            //이후 hash에 없는 상어 번호면 z에 추가, 있으면 그대로
            list = new ArrayList<>(z);
            if(list.size() == 1){
                System.out.println(answer);
                System.exit(0);
            }
            //그리고 list에 z의 상어들을 다시 재 삽임하여 list조절 끝. 1이면 answer출력
        }
        System.out.println(-1);
        //아니면 -1출력
    }
}

반갑습니다. 

주석을 달고 코드를 리뷰하는게 생각보다 반응이 좋아서 (좋아요 19개 첨입니다) 주석에 조금 더 신경을 썼습니다.

문제 이해가 그리 어렵지 않기 때문에 간략하게 요약하고 코드를 보겠습니다.

# 문제 요약

1. 자료 구조를 어떻게 이용해서 풀이할지가 가장 중요합니다. list를 활용해서 풀어냈지만 list종류가 여러가지라 헷갈릴 수 있습니다.

2. 모든 상어의 현재 위치에서 상어를 각각 모두 뿌리고 난 뒤 상어가 이동합니다. 이 부분에 주의하셔야합니다.

3. 이후 새로운 상어의 위치를 새로 담고 기존에 뿌린 가스는 다 1씩 감소시킵니다.

4. 새로운 상어의 위치를 구할 때 이동하지 못하는 곳은 없습니다. 자신이 뿌린 위치로 돌아갈 수 있기 때문입니다.

5. 겹치는 상어는 subList를 이용하여 커트할 수 있습니다.

 

코드로 봅시다.

static int n, m, k;
static List<Shark>[][] sharkList;
static List<Shark> list;
static List<Gas>[][] gasList;
static List<Integer>[][] dirList;
static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public static void main(String[] args) {

static으로는 다음과 같이 선언하였습니다.

shark타입으로 만든 것과 Gas타입으로 만든 것이 있으니 각각 어떤 클래스들인지 봅시다.

 

class Shark{
    int x;
    int y;
    int dir;
    int num;
    Shark(int x, int y, int dir, int num){
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.num = num;
    }
}
class Gas{
    int x;
    int y;
    int size;
    int num;
    Gas(int x, int y, int size, int num){
        this.x = x;
        this.y = y;
        this.size = size;
        this.num = num;
    }
}

Gas클래스를 굳이 만들지 않고 Shark를 써도 되지만.. 가스와 상어가 연관점이 전혀 없기도 해서 새로 만들었습니다.

취향껏 상어 클래스를 다형성의 성질을 이용하여 오버로딩하셔도 됩니다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
k = scan.nextInt();
dirList = new List[m][4];//방향 저장
sharkList = new List[n][n];//상어 위치를 배열에 저장
list = new ArrayList<>();//상어 저장
gasList = new List[n][n];//가스 위치를 배열에 저장

핵심 자료구조로는 이렇게 4개의 list를 이용할 것입니다.

굳이 sharkList가 있는데 list를 만드는 이유가 궁금하실 수 있어 미리 말씀드립니다.

sharkList에 있는 상어를 for문을 이용하여 loop탐색하려면 결국 2중 for문을 이용하여 각각 n까지 탐색해야 합니다.

그런데 상어가 가만히 있는 것이 아니라 이동할 수 있기 때문에 상어의 위치가 역전되어 기존에 탐색한 상어를 또 탐색할 수도 있어집니다...

따라서 별도의 list를 만들어서 관리하는 것이 훨씬 문제를 푸는데 수월해지실 것입니다. 

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        int x = scan.nextInt() - 1;
        sharkList[i][j] = new ArrayList<>();
        gasList[i][j] = new ArrayList<>();
        //sharkList와 gasList각 인덱스를 List로 선언함
        if(x >= 0) {
            sharkList[i][j].add(new Shark(i, j, -1, x));
            list.add(new Shark(i, j, -1, x));
        }
        //만약 x가 0보다 크-같으면 sharkList와 list에 각각 저장
    }
}

sharkList와 gasList를 arrayList로 각각 선언한 뒤 i,j,-1,x를 삽입할 것인데요.

-1은 음 default값으로 넣었습니다. 아무거나 넣으셔도 상관없습니다 ㅎ.

Collections.sort(list, new Comparator<Shark>() {
    @Override
    public int compare(Shark o1, Shark o2) {
        return o1.num - o2.num;
    }
});

이후 list를 정렬합니다.

저는 상어의 번호 순서대로 정렬할 것입니다. 왜냐하면 이 이후의 과정 때문인데요.

for(int i = 0; i < m; i++){
    int t = scan.nextInt() - 1;
    list.get(i).dir = t;
    sharkList[list.get(i).x][list.get(i).y].get(0).dir = t
    }

상어의 각 번호순서에 맞게 방향이 선언될 때 이걸 list에도 넣고 sharkList에도 넣어야 하기 때문에 그렇습니당.

for(int i = 0; i < m; i++)
    for(int j = 0; j < 4; j++)
        dirList[i][j] = new ArrayList<>();

이후 방향list도 m x 4 크기로 선언합니다.

int count = 0;
for(int i = 0; i < 4 * m; i++){
    ArrayList<Integer> temp = new ArrayList<>();
    for(int j = 0; j < 4; j++)
        temp.add(scan.nextInt() - 1);
    dirList[i / 4][count].addAll(temp);
    count++;
    if(count == 4)
        count = 0;
}

이 때에는 temp라는 임시 list를 생성하여 값이 4개 채워지면 dirList에 모두 삽입합니다.

count가 4씩 늘어날때마다 i / 4는 1씩 늘어나지요.

결국 각 상어별로 4가지의 방향에 대한 우선순위가 4개씩 저장할 수 있게됩니다.

다른분들은 어떻게 하셨는지 모르겠다만 저는 이게 제일 깔끔할거라 생각하여 그렇게했습니다.

자... 여기까지가 입력의 끝입니다.

이제 상어를 움직여보며 가스도 만들어 봅시다.

while (answer++ <= 1000){
    int size = list.size();
    for(int i = 0; i < size; i++) {
        Shark now = list.get(i);
        if (gasList[now.x][now.y].size() == 1)
            gasList[now.x][now.y].get(0).size = k;
        else if (gasList[now.x][now.y].size() == 0)
            gasList[now.x][now.y].add(new Gas(now.x, now.y, k, now.num));
    }

list의 크기만큼 상어를 움직일 것입니다.

while문이 한 번 이상 진행되고 난 뒤에 상어가 새로 위치한 인덱스에 한해 실행되는 구문입니다.

각 가스의 인덱스마다 가스가 들어 있는 곳이라면 (이전에 방문했던 곳에 또 온 것이므로) 가스의 size를 k로 조정합니다.

그리고 그렇지 않을 경우 (새로 방문하는 곳이므로) 가스를 새로 추가해줍니다.

이 구문은 처음 loop돌 때에는 실행되지 않습니다.

for(int i = 0; i < size; i++){
    Shark now = list.get(i);
    int nx = 0;
    int ny = 0;
    int d = 0;
    boolean isOk = false;
    ArrayList<Integer> temp = new ArrayList<>();
    for(int j = 0; j < 4; j++){
        d = dirList[now.num][now.dir].get(j);
        nx = now.x + dir[d][0];
        ny = now.y + dir[d][1];
        if(nx < 0 || ny < 0 || nx >= n || ny >= n)
            continue;
        if(gasList[nx][ny].size() == 0){
            isOk = true;
            break;
        }
        if(gasList[nx][ny].get(0).num == now.num){
            temp.add(nx);
            temp.add(ny);
            temp.add(d);
        }
    }

이후 size번 동안 상어의 새로운 위치를 배정해줄텐데요.

여기서 d구하는 부분이 많이 헷갈릴 수 있습니다....

제가 이건 잘 설명할 방법은 없는 것 같고, 이해하기를 바랄 뿐입니다 ㅠㅠ.... (궁금하심 댓글로)

그냥,, dirList에 현재방향과 j를 넣었을 때 해당 인덱스가 아무 것도 없으면 바로 break하셔서 쓰심 되고 가스가 있다면 temp에 값을 임시로 계속 저장해나가게 됩니다.

또한, 이럴 경우 isOk라는 변수를 이용하여 for문 밖으로 나왔을 때 새지점을 방문할 수 있는 점인지, 아님 내가 왔던 길을 되돌아 가야하는 점인지 판단을 해야합니다.

따라서

if(isOk){
    sharkList[now.x][now.y].remove(0);
    sharkList[nx][ny].add(new Shark(nx, ny, d, now.num));
    now.x = nx;
    now.y = ny;
    now.dir = d;
    //가스가 없는 인덱스를 찾으면 nx, ny삽입
}else{
    sharkList[now.x][now.y].remove(0);
    sharkList[temp.get(0)][temp.get(1)].add(new Shark(temp.get(0),temp.get(1),temp.get(2),now.num));
    now.x = temp.get(0);
    now.y = temp.get(1);
    now.dir = temp.get(2);
    //가스가 있는 인덱스만 있다면 우선순위에 따라 제일 먼저 넣은 temp이용
}

isOk가 true라면 sharkList에서 해당 인덱스를 제거하고 상어 위치를 새로 담으며 now.x와 now.y, now.dir를 수정합니다.

그러나 isOk가 false라면 nx, ny가 아니라 temp에 임시로 담아두었던 값들을 이용하여 위처럼 값을 갱신하여야 합니다.

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        if(gasList[i][j].size() == 1){
            gasList[i][j].get(0).size--;
            if(gasList[i][j].get(0).size == 0)
                gasList[i][j].remove(0);
        }
    }
}

이제부터는 정말 쉽습니다.

gasList가 있는 지점들은 모두 size를 감소시키며 gas가 0이면 해당 인덱스를 지워버립니다.

HashSet<Integer> hashSet = new HashSet<>();
for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        if(sharkList[i][j].size() > 1){
            Collections.sort(sharkList[i][j], new Comparator<Shark>() {
                @Override
                public int compare(Shark o1, Shark o2) {
                    return o1.num - o2.num;
                }
            });
            for(int z = 1; z < sharkList[i][j].size(); z++)
                hashSet.add(sharkList[i][j].get(z).num);
            sharkList[i][j] = new ArrayList<>(sharkList[i][j].subList(0, 1));
        }
    }
}

그리고 list에서 겹치는 상어를 제거하기 위해 hashSet에 상어 번호를 담은 뒤 제거하였습니다.

그 전에 먼저 상어가 2이상 있는 지점을 if문을 통해 찾은 뒤 num별로 오름차순으로 정렬하여 subList를 이용하여 커트하였습니다.

지금 쓰면서 생각난건데 이렇게 HashSet으로 커트해도 되지만 그냥 list에다가 삭제되는 num들을 매칭시켜서 서로 같으면 그 num들을 모두 0으로 바꾸어 버리고 내림차순으로 정렬한 뒤에 0인 것들은 전부 잘라도 되지 않을까 싶네요.

시간복잡도는 서로 비슷할 것 같아서 따로 시도해보진 않겠습니다 ㅎㅎ.

 

ArrayList<Shark> z = new ArrayList<>();
for(int i = 0; i < list.size(); i++)
    if(!hashSet.contains(list.get(i).num))
        z.add(list.get(i));
//이후 hash에 없는 상어 번호면 z에 추가, 있으면 그대로
list = new ArrayList<>(z);
if(list.size() == 1){
    System.out.println(answer);
    System.exit(0);
}
}
        System.out.println(-1);

네.. 그리고 뭐 list를 새로 갱신하고 answer를 출력해주시면 되는데요.

어려운건 없습니다만 구현 중에서도 빡센 난이도라 처음 코드 짤 때 문제 잘 보고 구현해야하는 문제입니다.

저는 가스를 뿌릴 때 상어별로 한 개씩 탐색하면서, 가스 뿌리고 상어 이동시키고 또 가스 뿌리고 상어 이동시키고 이걸 반복했더니 예제는 다 맞는데 정답이 틀리더군요.

다시보니까 가스를 미리 뿌리고 상어도 그 뒤에 따로 움직이는 거였는데 독해력이 딸려서인지 항상 이런 부분이 발목을 잡습니다.

어쨌든 긴 글 읽어주시느라 너무 감사합니다.

도움이 되셨길 바라겠습니다.