19236.청소년상어

이번에 풀어볼 문제는 백준 19236 청소년 상어이다. 괜찮은 문제인거 같다.

문제를 어느정도 풀면서 갑자기 느낀 것인데 정답률은 난이도가 아닌거 같다.

정답률이 높은 문제들은 구현만 제대로하면 다른 예외처리 같은 것이나 함정(히든케이스)같은 것이

없는 문제라 정답률이 높고 낮은 문제들은 함정(히든케이스)가 있어서 낮은거 같다는 생각이 들었다.

여튼 이 문제는 시뮬레이션 문제이다.

 

이 문제에서 얻어갈 수 있는 것은 idx에 대한 내용을 굳이 구조체의 변수로 가져가는 것이 아니라

배열의 순번으로 가져는 방법도 괜찮은 방법이다. 그리고 함수 로직의 순번에 대한 내용이다.

당연한 이야기지만 여러 함수들을 구현해야할 때는 큰 함수와 작은 함수에 대한 구별이 필요하고

큰 함수 속에 작은 함수가 들어가도록 구현하는 것이 좋다. 이 문제에서는 물고기가 먼저 이동하고

이동 후에 상어가 움직여서 물고기 이동 함수 이후 상어 함수를 호출해야 할 것 같지만

잘생각해보면 상어 이동 함수를 먼저 호출하고 그 내부에 물고기 이동 함수가 있는 게 구현이 수월하다.

참조 블로그 : yabmoons.tistory.com/495

 

---

 

< 구현 로직 >

1. 물고기 이동

=> 물고기는 빈칸이나 물고기가 존재하는 칸으로 갈 수 있고 물고기가 있다면 둘이 자리를 바꾼다.

=> 만약 가야하는 방향에 상어가 있거나 범위를 넘어선다면 반시계 방향으로 45도 틀어서 간다.

 

2.  물고기 이동 후에는 상어 이동

=> 상어는 자신이 먹은 물고기 방향으로 이동할 수 있고 이동거리는 최대 3이다.(4x4 map이므로)

 

3. 상어가 물고기를 먹을 수 있는 경우의 수가 여러개 존재하기때문에 위의 과정을 반복해야한다.

=> 재귀 사용 및 먹기 직전의 map을 저장해두었다가 다시 복귀하는 과정을 통해 최대값을 찾아낸다( Point !! )

 

---

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <string.h>
 
#define MAX 5
 
using namespace std;
 
int map[MAX][MAX];
int ans;
 
struct info{
    int x, y, dir;
    bool live;
};
 
info fish[17];
 
 
int dx[9] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[9] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
 
void showme(){
    for (int i = 0; i < 4; i++){
        for (int j = 0; j < 4; j++){
            printf("%2d ", map[i][j]);
        }
        cout << "\n";
    }
    cout << "\n";
}
 
 
bool area_check(int ax, int ay){ // 범위 초과 판단 함수
    if (ax < 0 || ay < 0 || ax >= 4 || ay >= 4)
        return false;
    return true;
}
 
void change(int idx1, int idx2){ // 물고기 위치 바꾸는 함수
    int tmp_x = fish[idx1].x;
    int tmp_y = fish[idx1].y;
    fish[idx1].x = fish[idx2].x;
    fish[idx1].y = fish[idx2].y;
    fish[idx2].x = tmp_x;
    fish[idx2].y = tmp_y;
}
 
void fish_mov(){ // 물고기 움직이는 함수
    for (int i = 1; i <= 16; i++){
        //showme();
        if (!fish[i].live)
            continue;
        int x = fish[i].x;
        int y = fish[i].y;
        int dir = fish[i].dir;
        int cnt = 0;
        for (int j = dir; j <= 8; j++){ // 물고기가 갈 수 있는 방향은 8가지이고 그 시작은 원래의 방향
            if (cnt == 8) // 8번의 방향이 바뀌었다면
                break;    // 탐색 종료
            int ax = x + dx[j];
            int ay = y + dy[j];
            if (!area_check(ax, ay) || map[ax][ay] == -1){ // 범위를 넘어서거나 상어를 만난경우 패스
                if (j == 8 && cnt < 8) // 아직 8번의 탐색이 끝나지 않았는데 8번째의 방향탐색을 했다면
                    j = 0; // 다시 1번의 방향부터 탐색
                cnt++; // 8번은 탐색에 사용했으므로 사용한 방향 카운트
                continue;
            }
 
            if (map[ax][ay] >= 1){ //물고기가 있는 경우
                change(i,map[ax][ay]); // 물고기 좌표 서로 바꿈
                fish[i].dir = j; // 방향 저장
                map[x][y] = map[ax][ay]; // 물고기 번호 서로 바꿈
                map[ax][ay] = i;         // 물고기 번호 서로 바꿈
                break;
            }
            else if (map[ax][ay] == 0){ // 빈칸인 경우
                map[ax][ay] = i; // 이동한 위치에 물고기 번호 저장
                map[x][y] = 0; // 이동 전 위치는 빈칸으로
                fish[i].x = ax;// 이동 좌표로 변경
                fish[i].y = ay;// 이동 좌표로 변경
                fish[i].dir = j;// 방향 저장
                break;
            }
            if (j == 8 && cnt < 8) // 아직 8번의 탐색이 끝나지 않았는데 8번째의 방향탐색을 했다면
                j = 0;  // 다시 1번의 방향부터 탐색
            cnt++; // 방향을 사용했으므로 사용한 방향 수 카운트
        }
    }
}
 
void eat(int x, int y, int ax, int ay, int idx, bool eat){
    if (eat == true){ // 먹는다.
        map[x][y] = 0;    // 상어 있던장소는 움직였으므로 비어짐
        map[ax][ay] = -1; // 해당 좌표로 상어이동
        fish[idx].live = false; // 해당 물고기는 두짐
    }
    else{ // 해당 물고기를 먹는걸 취소 ( 다른 경우를 확인하기 위함)
        map[x][y] = -1;        // 상어가 이전좌표로 돌아감
        map[ax][ay] = idx;     // 이동했던 좌표의 idx도 복구
        fish[idx].live = true; // 물고기 살아있음
    }
}
 
void func(int x, int y, int dir, int sum){ //재귀 함수
    ans = max(sum, ans);
 
    int c_map[MAX][MAX];
    info c_fish[17];
 
    memcpy(c_map, map, sizeof(map));   // map 저장해둠
    memcpy(c_fish, fish, sizeof(fish));// 물고기 정보버장
 
    fish_mov(); //물고기 이동
 
    for (int i = 1; i <= 3; i++){ // 상어가 갈 수 있는 최대 길이는 4*4 map에서 3이다.
        int ax = x + dx[dir] * i; // 곱하기를 이용하여 최대 3까지 갈 수있다는 것을 표현
        int ay = y + dy[dir] * i; // 곱하기를 이용하여 최대 3까지 갈 수있다는 것을 표현
        if (area_check(ax, ay)){  // 범위초과가 아닌 경우
            if (map[ax][ay] == 0) // 상어가 이동할 수 있는 좌표가 비어있는 경우 
                continue;         // 상어는 가지못하기 때문에 넘김
 
            int fish_idx = map[ax][ay];        // 상어가 먹는 물고기의 번호
            int fish_dir = fish[fish_idx].dir; // 상어가 먹는 물고기의 방향
 
            eat(x, y, ax, ay, fish_idx, true); // 해당 물고기 먹음
            func(ax, ay, fish_dir, sum + fish_idx); // 먹고나서 다음 탐색 진행
            eat(x, y, ax, ay, fish_idx, false);// 다른 경우의 수를 위해 먹었던거 복구
        }
    }
 
    memcpy(map, c_map, sizeof(map));   // 탐색이후 => 이전 map에서 정보 확인해야하므로 복구
    memcpy(fish, c_fish, sizeof(fish));// 탐색이후 => 이전 물고기 정보 확인해야하므로 복구
}
 
int main(){
    freopen("19236.txt", "r", stdin);
 
    int a, b;
    for (int i = 0; i < 4; i++){
        for (int j = 0; j < 4; j++){
            cin >> a >> b;
            map[i][j] = a; // map에 idx 저장
            fish[a] = { i, j, b, true }; // x, y, dir, live 정보 저장
        }
    }
 
    // 첫 번째 상어 셋팅
    int start_shark = map[0][0]; // 상어가 시작으로 먹는 물고기 값 저장
    map[0][0] = -1;              // 상어 표시
    fish[start_shark].live = false; // 해당물고기 먹힘 처리
    ans = 0;
    func(0,0,fish[start_shark].dir,start_shark); // 탐색 시작
 
    cout << ans << endl;
}