[ 백준-19236번 / 완전탐색 / 구현 ] 청소년 상어

1. 문제

---

문제

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

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부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

출력

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

예제 입력 1 복사

7 6 2 3 15 6 9 8 3 1 1 8 14 7 10 1 6 1 13 6 4 3 11 4 16 1 8 7 5 2 12 2

예제 출력 1 복사

33

 

 

2. 소스코드

---

1회차 - 2020/06/18

 

- 이런 문제는 풀때마다 어떤 자료구조를 사용할지 부터 생각하게 된다.

- 저장해야할 정보는 물고기의 위치, 번호, 방향 3가지 이다.

- 물고기의 번호가 1~16번으로 정해져있으므로, vector의 인덱스에 맞춰 물고기의 위치, 방향을 저장하기로 결정.

- 그런데 상어한테 잡혔는지, 안잡혔는지도 알아야해서 bool catched를 추가했다.

- 다음과 같은 구조체와 백터를 선언했다.

struct Info{

    int x, y, dir;
    bool catched;
    
};

vector <Info> fish(17);

- 그리고 배열, vector 등등 정보들을 구조체로 넘기기위해 한번 더 구조체로 묶었다.

- 이렇게 까지 생각하고 느낌대로 구현했는데, 굉장히 지저분한 코드가 나왔다.

 

 

 

 

 

- 소스코드

#pragma warning (disable : 4996)
#include <cstdio> 
#include <vector>
#define MAX 4
#define SHARK -1
using namespace std;

struct Info
{
    int x, y, dir;
    bool catched;
};

struct DATA
{
    int map[MAX][MAX], res;
    Info shark;
    vector<Info> fish;
}dt;

int ans;
int dx[] = {-1,-1,0,1,1,1,0,-1 };
int dy[] = {0,-1,-1,-1,0,1,1,1 };
 
void simulation(DATA dt) {

    //1)물고기를 움직인다.
    for (int i = 1; i < dt.fish.size(); ++i) {

        //잡힌 물고기는 넘어간다.
        if (dt.fish[i].catched) continue;

        int x = dt.fish[i].x;
        int y = dt.fish[i].y;
        int dir = dt.fish[i].dir;
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        //방향회전
        int cnt = 0;
        while (dt.map[nx][ny] == SHARK or (nx >= MAX or ny >= MAX or nx < 0 or ny < 0))
        {
            dir = (dir + 1) % 8;
            nx = x + dx[dir];
            ny = y + dy[dir];
            if (++cnt >= 8) break;
        }
        if (cnt >= 8) continue;

        dt.fish[i].dir = dir;

        if (dt.map[nx][ny]) {
            swap(dt.fish[i].x, dt.fish[dt.map[nx][ny]].x);
            swap(dt.fish[i].y, dt.fish[dt.map[nx][ny]].y);
        }
        else {
            dt.fish[i].x = nx;
            dt.fish[i].y = ny;
        }
        swap(dt.map[x][y], dt.map[nx][ny]);

    }//end for
 
    //2) 상어를 움직인다.
    while (true)
    {
        int x = dt.shark.x;
        int y = dt.shark.y;
        int dir = dt.shark.dir;
        int nx = x + dx[dir];
        int ny = y + dy[dir];
 
        while (nx < MAX and ny < MAX and nx >= 0 and ny >= 0)
        {
            if (dt.map[nx][ny]) {

                int fish_num = dt.map[nx][ny];

                //물고기를 잡아먹은 경우
                dt.fish[fish_num].catched = true;
                dt.res += fish_num;
                swap(dt.fish[fish_num].x, dt.shark.x);
                swap(dt.fish[fish_num].y, dt.shark.y);
                swap(dt.fish[fish_num].dir, dt.shark.dir);

                dt.map[nx][ny] = 0;
                swap(dt.map[nx][ny], dt.map[x][y]);

                simulation(dt);

                //잡아먹기 전으로 복구
                dt.fish[fish_num].catched = false;
                dt.res -= fish_num;
                swap(dt.fish[fish_num].x, dt.shark.x);
                swap(dt.fish[fish_num].y, dt.shark.y);
                swap(dt.fish[fish_num].dir, dt.shark.dir);

                swap(dt.map[nx][ny], dt.map[x][y]);
                dt.map[nx][ny] = fish_num;

            }
            //다음 칸움직임
            nx += dx[dir];
            ny += dy[dir];
        }
 
        //정답 갱신
        if (dt.res > ans) ans = dt.res;
        return;
    }

}
 
int main() {
    dt.fish.resize(17);

    for (int i = 0; i < MAX; ++i)
        for (int j = 0; j < MAX; ++j) {
            int dir;
            scanf("%d %d", &dt.map[i][j], &dir);
            dt.fish[dt.map[i][j]] = { i,j,dir - 1 };
            /*
            구조체 입력을 받을 때 위처럼 단 한 줄로 받을 수 있다.
            아래 코드와 같은 기능.

            dt.fish[dt.map[i][j]].x = i;
            dt.fish[dt.map[i][j]].y = j;
            dt.fish[dt.map[i][j]].dir = dir - 1;
            */
        }

    // 초기값 0,0의 물고기를 잡고 시작한다.
    dt.fish[dt.map[0][0]].catched = true;
    dt.shark.x = dt.shark.y = 0;
    dt.shark.dir = dt.fish[dt.map[0][0]].dir;
    dt.res = dt.map[0][0];
    dt.map[0][0] = SHARK;

    simulation(dt);

    printf("%d", ans);

    return 0;
}

 

그래서 아래 사항들을 조금 개선해봤다.

- 초기화 부분, 물고기를 먹는 부분 등의 코드 가독성이 매우 떨어짐.

- dfs인데 파라미터를 단순히 data를 넘기는 것 외에 이용하고 있지 않음. 파라미터를 이용해서 먹기 전/먹기 후 코드를 간략화.

 

- 조금 개선된 소스코드

#include <cstdio> 
#include <vector>
#include <algorithm>
 
#define MAX 4
using namespace std;

struct Info
{
    int x, y, dir;
    bool catched;
};

struct DATA
{
    int map[MAX][MAX];
    vector<Info> fish;
}dt;

int ans;
int dx[] = {-1,-1,0,1,1,1,0,-1 };
int dy[] = {0,-1,-1,-1,0,1,1,1 };
 
void simulation(DATA dt, int sx, int sy, int sdir, int res) {

    // 1) 상어가 현재 위치의 고기를 잡아먹는다.
    res += dt.map[sx][sy]; // 물고기 번호만큼 결과에 추가
    sdir = dt.fish[dt.map[sx][sy]].dir; // 상어가 물고기의 방향을 get
    dt.fish[dt.map[sx][sy]].catched = true; // 해당번호 물고기 잡힘
    dt.map[sx][sy] = 0; // map 상에서 0으로 변경

    // 2) 물고기를 움직인다.
    for (int i = 1; i < dt.fish.size(); ++i) {
        if (dt.fish[i].catched) continue;
        int x = dt.fish[i].x;
        int y = dt.fish[i].y;
        int dir = dt.fish[i].dir;
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        //방향회전
        int cnt = 0;
        while ((nx >= MAX or ny >= MAX or nx < 0 or ny < 0) or (nx == sx and ny == sy))
        {
            dir = (dir + 1) % 8;
            nx = x + dx[dir];
            ny = y + dy[dir];
            if (++cnt >= 8) break;
        }
        if (cnt >= 8) continue;

        dt.fish[i].dir = dir;

        if (dt.map[nx][ny]) {
            swap(dt.fish[i].x, dt.fish[dt.map[nx][ny]].x);
            swap(dt.fish[i].y, dt.fish[dt.map[nx][ny]].y);
        }
        else {
            dt.fish[i].x = nx;
            dt.fish[i].y = ny;
        }
        swap(dt.map[x][y], dt.map[nx][ny]);

    }//end for
    
    // 3) 상어를 움직인다.
    int snx = sx + dx[sdir];
    int sny = sy + dy[sdir];
    while (snx < MAX and sny < MAX and snx >= 0 and sny >= 0) {

        if (dt.map[snx][sny]) {
            simulation(dt, snx, sny, sdir, res);
        }
        snx += dx[sdir];
        sny += dy[sdir];
    }
    if (res > ans) ans = res;
    return;
}
 
int main() {
    dt.fish.resize(17);

    for (int i = 0; i < MAX; ++i)
        for (int j = 0; j < MAX; ++j) {
            int dir;
            scanf("%d %d", &dt.map[i][j], &dir);
            dt.fish[dt.map[i][j]] = { i,j,dir - 1 };
        }

    simulation(dt, 0, 0, 0, 0);

    printf("%d", ans);

    return 0;
}

 

디버깅팁

- 이런 문제는 디버깅할때, 콘솔창을 이용하는게 편한 것 같다.

- 아래의 함수를, 원하는 위치에 넣어 사용했다.

char arrow[8][3] = { {"↑"}, {"↖"}, {"←"}, {"↙"}, {"↓"}, {"↘"}, {"→"}, {"↗"} };

void showDT(DATA dt, int sx, int sy, int sdir, int res) {
    puts("");
    puts("현재 상황");
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {

            if (i == sx and j == sy){
                SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 4);
                printf("-1%s  ", arrow[sdir]);
                SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 15);
            }
            else
                printf("%2d%s  ", dt.map[i][j], arrow[dt.fish[dt.map[i][j]].dir]);
        }
        puts("");
    }
    printf("현재 상어의 방향! = %d\n", sdir);
    printf("현재 먹은 양! =  %d\n", res);
    printf("현재 상어 위치 =  %d %d\n", sx, sy);
    return;
}

- 그럼 다음과 같이, 현 상황을 한 눈에 파악할 수 있다.