[백준] 19236번 청소년 상어

19236 청소년 상어

문제

---

아기 상어가 성장해 청소년 상어가 되었다.

4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.

오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.

물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

입력

---

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

출력

---

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.

---

풀이)

재귀방법을 사용해 모든 경우를 다 확인해 본 문제이다.

풀이과정은 이러하다.

물고기들의 정보를 저장할 수 있게 구조체를 만든다.

struct Fish_info

{

int y,x,num,dir; // (위치, 번호, 방향을 저장)

};

물고기들의 위치를 저장할 이차원 4X4 배열을 만든다.

vector<vector<Fish_info>> map;

물고기들의 정보를 저장할 배열을 만든다.

vector<Fish_info> fish;

1. 맨 처음 상어가 (0,0)에 위치한 물고기를 잡아먹고, 그 물고기의 방향을 상어 방향으로 설정

2. 번호가 작은 물고기부터 방향에 맞게 이동

3. 상어가 본인 방향에 있는 물고기 있는 칸을 살핌

   3.1 먹을 물고기가 없다면 -> 이동할 수 있는 칸이 없다는 뜻. 종료 후 상어가 먹은 물고기들의 번호 계산

   3.2 먹을 물고기가 있다면 -> 각각 물고기를 먹었을 때를 살핌 즉, 2번 다시 수행

말로 설명하려니 어렵다. 코드를 보면서 이해하는 것이 빠를 것이다.

중요한 점은 재귀방법이니깐 임시 배열을 만들어서 저장한 뒤, 그 값을 바꿔줘야한다는 점이다.

코드)

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
 
struct Fish_info
{
    int y,x,num,dir;
    Fish_info() {
        this->y = 0;
        this->x = 0;
        this->num = 0;
        this->dir = 0;
    }
    Fish_info(int y,int x,int num, int dir) {
        this->y = y;
        this->x = x;
        this->num = num;
        this->dir = dir;
    }
};
 
Fish_info shark; // 상어 정보를 저장
vector<vector<Fish_info>> map; // 물고기들의 위치를 저장
int dy[9] = { 0,-1,-1,0,1,1,1,0,-1 }; // 이동방향 1~8번
int dx[9] = { 0,0,-1,-1,-1,0,1,1,1 };
vector<Fish_info> fish; // 물고기 정보를 저장
int result = 0;
 
void dfs(int hop, vector<vector<Fish_info>> &m, vector<Fish_info> &f) {
    vector<vector<Fish_info>> t_map = m;
    vector<Fish_info> t_fish = f;
    //물고기이동
    for (int i = 1; i < 17; i++) {
        if (t_fish[i].dir == 0) {//이미 상어에게 먹힌 고기라면 pass
            continue;
        }
 
        while (true) {//i번째 물고기가 이동할 수 있는 칸을 찾을때까지
            if (t_fish[i].dir == 9) t_fish[i].dir = 1; // 방향은 1~8번까지 밖에 없으니깐 
 
            int ny = t_fish[i].y + dy[t_fish[i].dir];
            int nx = t_fish[i].x + dx[t_fish[i].dir];
            if (ny < 0 || ny >= 4 || nx < 0 || nx >= 4) {//존재하지않는 칸
                t_fish[i].dir++; //45도 반시계회전
                continue;
            }
            if (ny == shark.y && nx == shark.x) {//상어가 있는 칸
                t_fish[i].dir++;
                continue;
            }
 
            //이동할수있는 칸 찾음, 물고기들끼리 위치 교환
            Fish_info temp = t_map[ny][nx]; //새로운 자리에 있는 물고기 정보 가져옴
 
            temp.y = t_fish[i].y; // 위치 변경해줌
            temp.x = t_fish[i].x;
            t_fish[i].y = ny; // 물고기 정보 저장 배열 update
            t_fish[i].x = nx;
            t_map[ny][nx] = t_fish[i]; //물고기 위치 저장 배열 update
            t_map[temp.y][temp.x] = temp;
            t_fish[temp.num].y = temp.y;
            t_fish[temp.num].x = temp.x;
            break;
        }
 
    }
 
    //상어이동    
    int ny = shark.y;
    int nx = shark.x;
    while (true) {
        ny += dy[shark.dir];
        nx += dx[shark.dir];
        if (ny < 0 || ny >= 4 || nx < 0 || nx >= 4) break; //더이상 이 방향으로 이동 불가
        if (t_fish[t_map[ny][nx].num].dir == 0) continue;//이미 먹은 물고기는 pass
        
        int num = t_map[ny][nx].num;//먹을 물고기 번호
 
        //dfs후 다시 원래대로 돌려놓기 위해 정보 저장해둠
        int tempf = t_fish[num].dir;
        int tempx = shark.x;
        int tempy = shark.y;
        int temps = shark.dir;
 
        shark.dir = t_fish[num].dir; //먹은 물고기의 방향 가짐
        t_fish[num].dir = 0;
        shark.y = t_fish[num].y;
        shark.x = t_fish[num].x;//상어위치 조정
        
        dfs(hop + num, t_map, t_fish);
        
        t_fish[num].dir = tempf;
        shark.x = tempx;
        shark.y = tempy;
        shark.dir = temps;
        
    }

    result = max(result, hop);
}
 
int main() {
    int a, b;
    for (int i = 0; i < 4; i++) {
        vector<Fish_info> element(4);
        map.push_back(element);
    }
    fish.resize(17);
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            scanf("%d %d", &a, &b);
            if (i == 0 && j == 0) {//상어가 (0,0)에 있는 물고기 먹음
                shark.y = i;
                shark.x = j;
                shark.dir = b;
                fish[a].dir = 0;//a번호 물고기는 죽은 물고기임을 표시
                result += a;
            }
            else {
                Fish_info temp = Fish_info(i, j, a, b);
                map[i][j] = temp;
                fish[a] = temp;

            } 
        }
    }
    dfs(result, map, fish);
    printf("%d", result);
    return 0;
}