[BOJ][삼성기출] 백준 19236번 - 청소년 상어 풀이

| |
백준 온라인 저지 19236번 - 청소년 상어 C++ 풀이 (삼성 SW 역량테스트 기출)


문제

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

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

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

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

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

1

<그림 1>

<그림 1>은 청소년 상어가 공간에 들어가기 전 초기 상태이다. 상어가 공간에 들어가면 (0, 0)에 있는 7번 물고기를 먹고, 상어의 방향은 ↘이 된다. <그림 2>는 상어가 들어간 직후의 상태를 나타낸다.

2

<그림 2>

이제 물고기가 이동해야 한다. 1번 물고기의 방향은 ↗이다. ↗ 방향에는 칸이 있고, 15번 물고기가 들어있다. 물고기가 있는 칸으로 이동할 때는 그 칸에 있는 물고기와 위치를 서로 바꿔야 한다. 따라서, 1번 물고기가 이동을 마치면 <그림 3>과 같아진다.

3

<그림 3>

2번 물고기의 방향은 ←인데, 그 방향에는 상어가 있으니 이동할 수 없다. 방향을 45도 반시계 회전을 하면 ↙가 되고, 이 칸에는 3번 물고기가 있다. 물고기가 있는 칸이니 서로 위치를 바꾸고, <그림 4>와 같아지게 된다.

4

<그림 4>

3번 물고기의 방향은 ↑이고, 존재하지 않는 칸이다. 45도 반시계 회전을 한 방향 ↖도 존재하지 않으니, 다시 회전을 한다. ← 방향에는 상어가 있으니 또 회전을 해야 한다. ↙ 방향에는 2번 물고기가 있으니 서로의 위치를 교환하면 된다. 이런 식으로 모든 물고기가 이동하면 <그림 5>와 같아진다.

5

<그림 5>

물고기가 모두 이동했으니 이제 상어가 이동할 순서이다. 상어의 방향은 ↘이고, 이동할 수 있는 칸은 12번 물고기가 있는 칸, 15번 물고기가 있는 칸, 8번 물고기가 있는 칸 중에 하나이다. 만약, 8번 물고기가 있는 칸으로 이동하면, <그림 6>과 같아지게 된다.

6

<그림 6>

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


입력

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


출력

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


풀이

이 문제는 백트래킹 과 시뮬레이션 이 결합된 형태의 문제로 삼성 기출문제 유형 중에서는 가장 까다로운 편에 속한다.

우선은 이 문제가 완전탐색 문제라는 것을 깨달아야 한다. 얼핏보면 먹을 수 있는 물고기 번호 합의 최댓값을 구하는 것이므로 매 턴마다 가장 큰 번호의 물고기를 먹으면 된다고 생각하고 탐욕법 으로 접근할 수도 있다. 하지만 당장은 큰 번호의 물고기를 먹더라도 그 번호의 물고기 방향에 따라서 추후 선택할 수 있는 물고기가 달라지기 때문에 탐욕법 이 아닌 완전탐색 으로 모든 경우의 수를 확인해봐야한다.

이 문제는 상당히 많은 양의 정보를 조작하기 때문에 사용할 자료구조의 고민도 필요하다. 모든 물고기마다 위치하는 좌표와 방향, 그리고 번호가 있다. 맵에는 격자마다 위치한 물고기의 번호가 있다. 또 물고기의 이동 시에는 작은 번호부터 접근하여 이동시킬 수 있어야한다. 필자는 물고기를 구조체 로 표현한 후 1번 물고기부터 16번 물고기를 순차적으로 담은 vector 를 선언하여 각각의 물고기에 수월하게 접근할 수 있도록 하였다. 또한 4x4 배열을 선언하고 실시간으로 해당 격자 위치의 물고기 번호를 저장해두었다.

그리고 이 문제는 어디까지나 시뮬레이션 문제로 조건이 아주 많으므로 문제를 정말 꼼꼼히 읽어야한다. 눈여겨봐야할 조건들은 다음과 같다.

  • 물고기는 빈 칸으로 이동하거나 다른 물고기와 위치를 바꿀 수 있다.
  • 물고기가 이동할 수 없는 경우에는 움직이지 않는다.
  • 상어는 물고기가 없는 칸으로는 이동할 수 없다.
  • 상어는 먹은 물고기의 방향을 따라간다.

마지막으로 재귀함수 를 이용해 백트래킹 을 구현하려면 이 시뮬레이션 의 순환구조를 파악해야한다. 상어가 (0,0) 좌표의 물고기를 잡아먹는 것으로 시작하여 물고기의 이동이 일어나고 다시 상어가 다른 물고기를 잡아먹으므로 다음과 같은 함수를 떠올릴 수 있다.

solve(y,x) = (y,x) 좌표를 먹고 물고기들의 이동 후 먹은 번호 누적 합 반환

위 함수를 재귀적으로 수행하여 백트래킹 으로 모든 시뮬레이션 의 결과를 확인할 수 있다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <vector>
using namespace std;

struct Fish{
    int y,x,d,n;
    Fish(int y, int x, int d, int n):y(y),x(x),d(d),n(n){}
};

const int dy[]={-1,-1,0,1,1,1,0,-1};
const int dx[]={0,-1,-1,-1,0,1,1,1};

bool inRange(int y, int x){
    return y>=0 && x>=0 && y<4 && x<4;
}

int solve(int y, int x, vector<vector<int>> field, vector<Fish> fishes){
    int ret,d;
    Fish& eaten = fishes[field[y][x]]; // 먹은 물고기

    d=eaten.d; // 상어 방향 전환
    ret=eaten.n;

    // 먹은 물고기의 빈칸 전환
    eaten.d=-1;
    field[y][x]=-1;

    // 모든 물고기 이동
    for(Fish& f:fishes){
        if(f.d==-1) continue; // 빈칸일 경우

        bool fail=false;
        int ny,nx,fd=f.d;

        while(true){
            ny=f.y+dy[f.d];
            nx=f.x+dx[f.d];

            if(inRange(ny,nx)&&(ny!=y||nx!=x)) break;

            if(++f.d>7) f.d=0; // 반시계 방향 회전

            if(f.d==fd){ // 이동할 수 있는 곳이 없을 경우
                fail=true;
                break;
            }
        }

        if(fail) continue;

        if(field[ny][nx]!=-1){ // 다른 물고기와 위치 변경
            fishes[field[ny][nx]].y=f.y;
            fishes[field[ny][nx]].x=f.x;
        }

        field[f.y][f.x]=field[ny][nx];
        field[ny][nx]=f.n-1;
        f.y=ny;
        f.x=nx;
    }

    // 백트래킹
    int ny=y, nx=x;
    while(true){
        ny+=dy[d];
        nx+=dx[d];

        if(!inRange(ny,nx)) break;
        if(field[ny][nx]==-1) continue;

        ret=max(ret,eaten.n+solve(ny,nx,field,fishes));
    }

    return ret;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    vector<Fish> fishes(16,Fish(0,0,0,0));
    vector<vector<int>> field(4,vector<int>(4));

    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            int n,d; cin>>n>>d;
            fishes[n-1].y=i;
            fishes[n-1].x=j;
            fishes[n-1].d=d-1;
            fishes[n-1].n=n;
            field[i][j]=n-1;
        }
    }

    cout<<solve(0,0,field,fishes);

    return 0;
}
0%