[백준] 19236: 청소년 상어(C++)

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

19236번: 청소년 상어

 

소요 시간

골드 2 기준 1시간 30분 정도가 소요되었는데, 중간에 남자친구랑 노닥거렸습니다. 빡집중 한시간 정도로 생각하시면 될 듯.

 

 

구상

문제는 1) 상어 투입 2) 물고기 이동 3) 상어 이동을 수행하고 2)와 3)을 반복해야 합니다. 또한, 최댓값을 구하는 문제이기 때문에 dfs, 종료조건이 있기 때문에 백트래킹을 사용했습니다. 2)와 3)이 dfs 로직 내에 들어 있었습니다.

1) 상어 투입은 그냥 0,0에 투입하면 됩니다.

2) 물고기 이동은 현재 map상태 뿐만 아니라 물고기 index별 위치를 저장하는 벡터를 추가적으로 관리하여 각 물고기별로 이동시켰습니다. 모든 방향이 막혔는지 꼭 판단하여 이동을 하지 않도록 했습니다.

3) 상어를 이동하는 과정은 재귀적으로 했습니다.

 - 갈 수 있는 모든 칸들에 대해, 해당 칸에 물고기가 없거나 범위를 초과하면 무시합니다.

 - 물고기가 있는 칸으로 상어를 이동시키고, 2)부터 재귀호출합니다.

 - 재귀호출이 끝나면, 상어 원 위치, 방금 물고기를 잡아먹은 칸을 복구합니다.

 4) 지금 상태에서 가능한 모든 상어 이동을 탐색했으면, *물고기 이동을 무효화하고* 종료합니다.

 

코드

#include <string>
#include <vector>
#include<iostream>
#include <climits>
#include<queue>
#include<cmath>
#include<algorithm>

using namespace std;
vector<vector<pair<int, int> > > board; 
vector<pair<int, int> > fishes; //fish idx - x,y position
int answer = 0;
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, -1, -1, -1, 0, 1, 1, 1};

void move_fish() {
    for(int i=1; i<=16; i++) {
        int x = fishes[i].first; int y = fishes[i].second;
        if(x == -1 && y == -1) continue;
        int dir = board[x][y].second;
        int nx = x + dx[dir]; int ny = y + dy[dir];
        int ndir = dir;
        bool cannotMove = false;
        while(nx < 0 || nx > 3 || ny < 0 || ny > 3 || board[nx][ny].first == -1) {
            ndir += 1; ndir %= 8;
            nx = x + dx[ndir]; ny = y + dy[ndir];
            if(ndir == dir) {
                cannotMove = true;
                break;
            }
        }
        if(cannotMove) continue;
        else {
            pair<int, int> otherFish = board[nx][ny];
            board[nx][ny] = board[x][y];
            board[nx][ny].second = ndir;
            board[x][y] = otherFish;
            fishes[otherFish.first] = pair<int, int>(x, y);
            fishes[i] = pair<int, int>(nx, ny);
        }
    }
}

void dfs(int x, int y, int result) { //shark position, total number
    answer = max(answer, result);
    vector<vector<pair<int, int> > > prev_board(board.size());
    copy(board.begin(), board.end(), prev_board.begin()); 
    vector<pair<int, int> > prev_fishes(fishes.size()); //fish idx - x,y position
    copy(fishes.begin(), fishes.end(), prev_fishes.begin());

    move_fish();
    int dir = board[x][y].second;
    int nx = x; int ny = y;
    for(int i=0; i<3; i++) {
        nx += dx[dir]; ny += dy[dir];
        if(nx < 0 || nx > 3 || ny < 0 || ny > 3 || board[nx][ny].first == 0) continue;
        else {
            int num = board[nx][ny].first;
            int ndir = board[nx][ny].second;
            pair<int, int> p = fishes[num];

            fishes[num] = pair<int, int>(-1, -1);
            board[nx][ny].first = -1;
            board[x][y].first = 0;
            dfs(nx, ny, result + num);
            board[nx][ny].first = num;
            board[nx][ny].second = ndir;
            fishes[num] = p;
            board[x][y].first = -1;
            board[x][y].second = dir;
        }
    }
    board = prev_board;
    fishes = prev_fishes;

}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    board.resize(4);
    fishes.resize(17);
    for(int i=0; i<4; i++) {
        board[i].resize(4);
        for(int j=0; j<4; j++) {
            cin >> board[i][j].first >> board[i][j].second;
            board[i][j].second -= 1;
            fishes[board[i][j].first] = pair<int, int>(i, j);
        }
    }

    int tmp = board[0][0].first;
    fishes[board[0][0].first] = pair<int, int>(-1, -1);
    board[0][0].first = -1;
    dfs(0,0,tmp);
    cout << answer << endl;

    return 0;
}