청소년 상어

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 0142 ~ 0400
int ans;
pair<int,int> origin[4][4]; // 번호, 방향
int dx[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
pair<pair<int,int>,int> shark_o; // {{r,c},d}
deque<pair<int,int>> fish_o(16);
int rotate(int d){
    d++;
    if(d > 7) d -= 8;
    return d;
}
void DFS(int tot, pair<int,int> board[4][4], pair<pair<int,int>,int> shark, deque<pair<int,int>> fish){
    // 1) 물고기 이동
    for(int i=0;i<fish.size();i++)
    {
        auto cur = fish[i];
        if(cur.first == -1) continue;
        int dir = board[cur.first][cur.second].second;
        int ny = cur.first + dy[dir];
        int nx = cur.second + dx[dir];
        /* 범위를 벗어났거나 상어가 있는 곳이면 45도 회전 */
        if((nx<0 or ny<0 or nx>=4 or ny>=4) or (shark.first.first == ny and shark.first.second == nx)){
            dir = rotate(dir);
            board[cur.first][cur.second].second = dir;
            i--;
            continue;
        }
        /* 물고기 이동 */
        auto tmp = board[ny][nx];
        /* 물고기가 있는 칸이면 서로 좌표 교환 */
        if(tmp.first != -1){
            auto save = fish[tmp.first-1];
            fish[tmp.first-1] = fish[i];
            fish[i] = save;
        }else fish[i] = {ny,nx};
        /* board교환 */
        board[ny][nx] = board[cur.first][cur.second];
        board[cur.first][cur.second] = tmp;
    }

    // 2) 상어 이동
    int ny = shark.first.first;
    int nx = shark.first.second;
    while(true)
    {
        /* 새로운 보드, 샤크, 피쉬 생성 */
        pair<int,int> t_board[4][4];
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                t_board[i][j] = board[i][j];
        pair<pair<int,int>,int> t_shark = shark; 
        deque<pair<int,int>> t_fish(fish.begin(), fish.end());

        int dir = t_shark.second;
        ny += dy[dir];
        nx += dx[dir];
        if(nx<0 or ny<0 or nx>=4 or ny>=4) goto stop;
        if(t_board[ny][nx].first == -1) continue; // 물고기가 없으면 pass

        int num = t_board[ny][nx].first;
        t_fish[num-1] = {-1,-1};
        t_shark.first = {ny,nx};
        t_shark.second = t_board[ny][nx].second;
        t_board[ny][nx] = {-1, -1};
        ans = max(ans, tot + num);
        DFS(tot + num, t_board, t_shark, t_fish);
    }
    stop:;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
        {
            int a,b;
            cin >> a >> b;
            origin[i][j] = {a,b-1}; // 번호, 방향
            fish_o[a-1] = {i,j}; // i번 물고기 인덱스 = i-1
        }
    auto tmp = origin[0][0];
    int num = tmp.first;
    origin[0][0] = {-1,-1};
    fish_o[num-1] = {-1,-1}; // 물고기 삭제
    shark_o = {{0,0},tmp.second};

    /* 새로운 보드, 샤크, 피쉬 생성 */
    pair<int,int> t_board[4][4];
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            t_board[i][j] = origin[i][j];
    pair<pair<int,int>,int> t_shark = shark_o; 
    deque<pair<int,int>> t_fish(fish_o.begin(), fish_o.end());
    DFS(num, t_board, t_shark, t_fish);

    cout << ans;
    return 0;
}

• 문제 풀이 접근
  • 상어가 어떤 물고기를 먹는지에 따라 결과가 계속 달라짐
    --> DFS를 이용한 완전탐색 필요

• 고려해야할 것
  • 순서가 진행될 때 마다 board / shark / fish 변수가 달라진다
    --> 매번 매개변수로 새로운 배열을 넘기거나 다시 배열을 복구해주는 방법이 있다
    (여기서 나는 매번 매개변수로 새로운 배열을 넘기는 방법을 선택함)

• 오래걸린 이유
  • 물고기가 없는 경우에 board만 갱신하고, fish[]를 갱신하지 않음
    --> 필요한 데이터를 분산시켜 저장해서 실수를 유발함 --> 구조체 사용
  • dx[] / dy[] 방향 지정시 오타가 있었다
    --> 꼼꼼하게 체크하자
  • rotate()를 통해 반시계 45도 회전을 했는데 시계방향으로 했다
    --> 역시 꼼꼼하게 체크하자

• 느낀 것
  • DFS를 이용한 완전탐색을 할 때 board나 map을 가지며 변경이 될 때 2가지 방법을 고민하자
    1) 매번 새로운 변수를 만들어서 매개변수로 넘기는 방법
       : 매개변수로 값이 복사되며 발생하는 시간복잡도를 고려해야 한다
         --> 크기가 작을 때 가능
    2) 백트래킹 (DFS 수행 후 변수 복구)
       : copy하는 함수를 별도로 만들거나 직접 반복문을 돌려서 복구
        (시간복잡도 측면에서 백트래킹 방법이 더 안전해 보임)
  • 구조체를 사용해보자
    : 오래걸린 이유중 하나가 무조건 pair<>을 쓰려는 경향 때문에 필요한 데이터가 분산되어 관리하고 유지하기 까다로워 실수를 발생시켰기 때문
    --> 다음부터는 구조체를 써서 필요한 데이터를 응집시켜서 활용하자