[백준, BOJ_19236]

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

19236번: 청소년 상어

 

 

 

[청소년 상어]

 

S전자 DS SW테스트를 복원해서 만든 문제

 

실제 테스트에서 소요시간 2시간 걸렸었다.

문제의 경우 전형적인 시뮬레이션 구현 문제로, 지문를 잘 이해하고 지문대로 구현하면 끝이 난다. ( 실제론 자잘한 오류들을 잡아내다가 시간을 너무 많이 사용함..)

 

당시의 기억을 살리면서 문제를 풀어보았다.

 

크게 구현해야 할 부분은,

1. 상어를 방향대로 이동시켜서 해당 위치에 있는 물고기를 잡아먹는 것에 대한 부분

2. 물고기들을 1번부터 차례대로 이동시키는 부분

으로 생각할 수 있다.

 

그래서 우선 물고기 및 상어의 방향성을 아래와 같이 지문대로 설정해주었다.

 

    public static void moveFish(ArrayList<Fishes> f){
        
        // 1번부터 순서대로 이동
        for(int i=1;i<=16;i++){
            Fishes fish = new Fishes(0,0,0,0);
            for(Fishes ftmp : f){
                if(i==ftmp.number) {
                    fish = ftmp;
                    break;
                }
            }
            // 이미 잡힌 물고기인 경우
            if(fish.number==0) continue;
            int dir = fish.dir;
            while(true){
                // 이동여부 확인 3
                int r = isMove(f, i, fish.x, fish.y, dir);
                // 해당위치가 범위가 밖이거나 상어인 경우 방향을 회전시킴.
                if(r==-1){
                    dir++;
                    // 8보다 커지면 맨처음으로
                    if(dir>8){
                        dir = 1;
                    }
                }
                // 빈칸 이동
                else if(r==-2){
                    int nx = fish.x + dx[dir];
                    int ny = fish.y + dy[dir];
                    fish.x = nx;
                    fish.y = ny;
                    fish.dir = dir;
                    
                    break;
                }
                // swap , 해당 위치의 물고기 번호와 방향만 재설정해서 바꾼다.
                else {
 
                    int tmpNumber = fish.number;
                    
                    Fishes swapFish = f.get(r);
                    
                    fish.number = swapFish.number;
                    fish.dir = swapFish.dir;
                    
                    swapFish.number = tmpNumber;
                    swapFish.dir = dir;
                    
                    break;
                }
            }
            
        }
        
        
    }
    public static int isMove(ArrayList<Fishes> f, int idx, int x, int y, int dir){
        
        int nx = x+dx[dir];
        int ny = y+dy[dir];
        
        // 다음 위치가 이동할 수 없는 위치인 경우 -1
        if(nx<0 || ny<0 || nx>=4 || ny>=4 || (nx==sharkX && ny==sharkY)) return -1;
        
        // 해당위치에 물고기가 있는지 찾음.
        for(int i=0;i<f.size();i++){
            if(f.get(i).number==idx) continue;
            Fishes fish = f.get(i);
            if(nx==fish.x && ny==fish.y) return i;
        }
        // 이동할 수는 있지만, 해당 위치가 빈칸인 경우
        return -2;
    }

 

 

 

전체적으로 구현 난이도가 높았던 것은 아니라고 생각되나,

시험의 긴장감이 더해지면서 실수하는 부분들이 많이 생겼고 이를 고치고 찾아내는 데에 시간이 많이 걸렸었다.

 

 

ArrayList 가 재귀를 돌면서 값이 변형이 발생이 된다 ( 값 전달에서 참조자료형 변수를 넘겨주면 래퍼런스를 ,주소를 가리키는 레퍼런스를 전달한다.)

 

 

또 실수한 부분은, 

isMove 리턴 값을 -2 가 아닌 0으로 하여서 문제가 생겼다. ArrayList에서 가장 맨 처음 인덱스 0으로 리턴이 for문에서도 리턴이 되어 물고기 이동이 정상적으로 일어나지 않았다.

 

마찬가지로 , isMove에서 물고기끼리 자리를 바꿀 때 숫자만 바꿔주면 되는데 위치까지 다 변경해버려 물고기 이동이 제대로 안되었다.. 

 

 

총평 : 

 

보다 더 빠르게 풀 수 있는 문제라고 생각이 되고,

문제를 풀 때 보다 더 생각이나 구조를 정확하게 잡고 풀어나가야겠다고 느꼈다.

 

운이 좋아서 최종 면접까지 갔으나, 면접 결과는 아직 발표 전이므로 다음 하반기까지 SW 테스트를 대비해

문제들을 풀면서 정확성과 속도를 키워야 할 것이다.

 

전체 소스코드는 아래에 

 

https://github.com/Yuhyeonmo/Data_Structure/blob/master/algo/BOJ_19236.java