백준 19236 청소년 상어 : 내가 했던 4가지 놓친 점들과 함께

문제 링크

www.acmicpc.net/problem/19236

풀이 아이디어

사실 풀이 아이디어는 간단했다. 4*4의 제한된 공간과 가능한 경우 중 최댓값을 찾는 문제.

완전 탐색이다.

 

문제에서 말하고 있는 대로, 상어를 이동시키기 전 물고기들을 전부 이동시킨 후, 

이동할 수 있는 상어를 백트래킹을 통해 탐색하면 되는 문제였다.

나는 이 문제를 풀면서 몇 가지 실수들을 했었는데, 우선 최종 solved 받은 코드를 보고 이야기를 해보겠다.

코드

#include <bits/stdc++.h>
using namespace std;

int fisharr[4][4];
int dirarr[4][4];
int answer=0;
int dx[8] = {0,-1,-1,-1,0,1,1,1};
int dy[8] = {-1,-1,0,1,1,1,0,-1};
bool visited[4][4];

void dfs(int y, int x, int cost, int cnt){ //dfs로 탐색하는게 더 편할지도?


    //현재 fisharr과 dirarr를 복사시켜놓기.
    int tmpfisharr[4][4];
    int tmpdirarr[4][4];
    for(int i=0; i<4; i++){
        for(int j=0; j<4; j++){
            tmpfisharr[i][j]=fisharr[i][j];
            tmpdirarr[i][j]=dirarr[i][j];
        }
    }

    fisharr[y][x]=-1;
    visited[y][x]=true;

    //1번부터 물고기 이동시키기 - 정상작동
    for(int fish=1;fish<=16;fish++) {
        for (int y = 0; y < 4; y++) {
            for (int x = 0; x < 4; x++) {
                if (fisharr[y][x] == fish) {

                    int fishdir = dirarr[y][x];
                    for(int i=0; i<8; i++){
                        int j = (i+fishdir) % 8;
                        int newy = y+dy[j];
                        int newx = x+dx[j];
                        if(newy<0||newy==4||newx<0||newx==4||fisharr[newy][newx]==-1) {
                            continue;
                        }
                        //바꾸려는 물고기를 찾았음.
                        int targetfish = fisharr[newy][newx];

                        //y,x 값과 newy,newx 값을 서로 바꾼다. 방향과 물고기 숫자 값 둘다.
                        int tmp = fisharr[y][x];
                        fisharr[y][x] = fisharr[newy][newx];
                        fisharr[newy][newx] = tmp;
                        tmp = dirarr[y][x];
                        dirarr[y][x] = dirarr[newy][newx];
                        //실수 2. 물고기 위치는 서로 바뀌지만 방향은 예전꺼 그대로 바꿔치기 하면 안된다. 한놈은 업데이트 된방향으로 저장해야함.
                        dirarr[newy][newx] = j;

                        //실수1. break문.
                        break;
                    }
                    x=4;
                    y=4;
                    //실수1. break문
                    break;
                }

            }
        }
    }
    //이동 끝
//    cout<<"\n\n";
//    for(int i=0; i<4; i++) {
//        for (int j = 0; j < 4; j++) {
//            cout<<fisharr[i][j]<<" ";
//        }
//        cout<<"\n";
//    }
//    cout<<"\n";
//    for(int i=0; i<4; i++) {
//        for (int j = 0; j < 4; j++) {
//            cout<<dirarr[i][j]<<" ";
//        }
//        cout<<"\n";
//    }
//    cout<<"\n";
    //물고기는 빈칸으로도 이동할 수 있다. 빈칸은 따라서 0으로 처리해 줘야함.
    fisharr[y][x]=0;
    //상어가 이동할 수 있는 경우의 수를 count한다. count==0일시 답 갱신
    int count=0;
    int idx = dirarr[y][x];

    for(int i=0; i<3; i++){
        y+=dy[idx];
        x+=dx[idx];
        if(y<0||y==4||x<0||x==4)
            break;
        //실수 3: 빈칸은 상어가 갈 수 없다. 이조건 추가하니 예제 1,3,4 통과
        if(fisharr[y][x]==0) continue;
        else{
            count++;
            dfs(y,x,cost+fisharr[y][x],cnt+1);
        }
    }
    if(count==0) {
        answer = max(answer, cost);
        //실수4. return;을 여기서 하면 안된다.
    }
    //원래대로
    for(int i=0; i<4; i++){
        for(int j=0; j<4; j++){
            fisharr[i][j]=tmpfisharr[i][j];
            dirarr[i][j]=tmpdirarr[i][j];
        }
    }


}


int main(){
    int fish,direction;
    for(int y=0; y<4;y++){
        for(int x=0; x<4; x++){
            cin>>fish>>direction;
            fisharr[y][x] = fish;
            dirarr[y][x] = direction-1;
        }
    }
    dfs(0,0,fisharr[0][0],0);

    cout<<answer;
}

실수1. break를 적절히 사용하지 못한 점

1번부터 16번 물고기를 이동시킬때, 

한 물고기의 위치를 2차원 배열 탐색시 발견했으면, 

위치를 바꾼 후 break문 배치를 통해 다음 번호의 물고기로 넘어갔어야 했는데 그렇게 하질 못했다.

 

실수2. 뱡향은 바뀐 상태로 유지한 채 바꿔줘야 한다.

문제를 제대로 파악하지 못하고 풀어서 일어난 참사.

 

실수3. 빈칸에는 상어가 이동할 수 없다.

이부분은 문제를 풀기 전에 염두해 두고 있던 부분인데 아쉽게 풀 때 까먹어 버린 나머지,

백트래킹에서 무한 재귀에 빠져버리는 걸 보고 캐치해냈다.

 

실수 4. return; 안하기.

사실 이건 실수가 아니라 실력인데, 백트래킹에서는 탐색이 끝나면 return;을 해주면 안된다.

백트래킹이 끝나고 배열을 복원해놓는 과정이 생략이 되어버리기 때문에 데이터가 꼬여버리게 된다.

 

 

알고리즘도 오랜만에 풀어보고 구현이 복잡해서 시간이 좀 걸렸다.

진짜 알고리즘은 꾸준히 해야 되는 것 같다.