[Algorithm] 2020 상반기 삼성전자 코딩테스트 오전 - 청소년 상어(c++)

완벽한 백트래킹(dfs)문제이다.

 

dfs 함수에서 모든 상태를 새로운 배열과 벡터에 담아두고

물고기를 움직이고, 상어를 움직인 후 재귀함수를 통해 계속 반복한다.

그 후 재귀에서 돌아오면 다시 담아두었던 새로운 배열과 벡터의 값들을 원래 배열과 벡터에 넣어주면 된다.

 

즉, 계속 백트래킹을 하면서 원래대로 돌려놓는 작업이 중요하다!

 

코드첨부

// 청소년 상어
#include <iostream>
using namespace std;
 
int num, dir;
int ans = 0;
pair<int, int> sea[5][5];
int dx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[8] = { 0, -1, -1, -1, 0, 1, 1, 1 };
 
struct FISH {
    int x, y, dir;
    bool die;
};
 
void copySea(pair<int, int> a[5][5], pair<int, int> b[5][5]) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            a[i][j] = make_pair(b[i][j].first, b[i][j].second);
        }
    }
}
 
void copyFish(FISH a[17], FISH b[17])
{
    for (int i = 1; i <= 16; i++) {
        a[i].x = b[i].x;
        a[i].y = b[i].y;
        a[i].dir = b[i].dir;
        a[i].die = b[i].die;
    }
}
 
void move(int sharkX, int sharkY, int sharkDir, FISH f[17], pair<int, int> s[5][5], int eat){
    pair<int, int> sea[5][5];
    FISH fish[17];
    copySea(sea, s);
    copyFish(fish, f);
 
    // 상어가 물고기 먹기
    fish[sea[sharkX][sharkY].first].die = true;
    // 그 자리에 있던 물고기 죽이기
    sea[sharkX][sharkY] = make_pair(0, 0);
 
    // 물고기 이동하기
    for(int i=1; i<=16; i++){
        if(fish[i].die==true) continue;
        int x = fish[i].x;
        int y = fish[i].y;
        int dir = fish[i].dir;
        int nx = x+dx[dir-1];
        int ny = y+dy[dir-1];
 
        bool check = false;
        int temp = 0;
 
        // 경계를 넘거나 상어가 있는 곳이면 반시계방향으로 틀어
        while((nx<0 || nx>=4 || ny<0 || ny>=4) || (nx==sharkX && ny==sharkY)){
            temp++;
            if(temp==8){
                check = true;
                break;
            }
 
            dir++;
            if(dir==9){
                dir = 1;
            }
 
            nx = x+dx[dir-1];
            ny = y+dy[dir-1];
        }
 
        // 이동할 곳이 있다.(자리 교환)
        if(check==false){
            int num = i;
            int next_num = sea[nx][ny].first;
            int next_dir = sea[nx][ny].second;
 
            sea[x][y] = make_pair(next_num, next_dir);
            sea[nx][ny] = make_pair(num, dir);
 
            fish[next_num].x = x;
            fish[next_num].y = y;
 
            fish[num].dir = dir;
            fish[num].x = nx;
            fish[num].y = ny;
        }
    }
 
    int nx = sharkX+dx[sharkDir-1];
    int ny = sharkY+dy[sharkDir-1];
 
    while(0 <= nx && nx < 4 && 0 <= ny && ny < 4){
        if(sea[nx][ny].first!=0){
            move(nx, ny, sea[nx][ny].second, fish, sea, eat+sea[nx][ny].first);
        }
        
        nx += dx[sharkDir - 1];
        ny += dy[sharkDir - 1];
    }
 
    ans = max(ans, eat);
}
 
 
int main()
{
    FISH fish[17];
    for(int i=0; i<4; i++){
        for(int j=0; j<4; j++){
            cin>>num>>dir;
            sea[i][j] = make_pair(num, dir);
            fish[num].die = false;
            fish[num].dir = dir;
            fish[num].x = i;
            fish[num].y = j;
        }
    }
 
    move(0, 0, sea[0][0].second, fish, sea, sea[0][0].first);
 
    cout<<ans<<"\n";
 
    return 0;
}

 

문제 첨부

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

19236번: 청소년 상어