2020 상반기 삼성SW역량테스트 :: 청소년 상어

문제

문제 링크

문제접근

조건이 복잡해서 꽤 까다로운 문제였습니다.
푸는데 2시간 정도 소요됐습니다.

문제 분해하기

문제에 주어진 조건이 복잡합니다. 차근차근 문제를 분해해봅시다.

• 상어는 항상 (0, 0)에서 시작합니다.
• 물고기는 작은 번호부터 움직입니다.
  • 이동할 수 없는 경우 반시계방향으로 45도 방향을 바꿉니다.
    • 상어가 있는 칸으로 이동할 수 없습니다.
    • 공간의 경계를 넘을 수 없습니다.
  • 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꿉니다.
• 상어는 한 번에 여러 칸을 이동할 수 있습니다.
  • 상어는 잡아먹은 물고기의 방향을 따라갑니다.

결과적으로 이 문제를 풀기 위해서는 크게 3가지 조건을, 작게는 8가지 조건을 모두 만족할 수 있어야 합니다. 작은 조건 하나라도 놓치지 않게끔 체크해가며 문제를 풀어봅시다.

문제 풀이과정

1. 상어에 대한 정보를 의미하는 custom 구조체 SharkInfo를 만듭니다.

   • 상어의 현재 좌표와 방향 정보를 포함합니다.

2. 어느정도 문제를 풀어보신 분이라면 이 문제가 greedy로 풀면 위험하다는 것을 직감적으로 알 수 있습니다. 바로 방향이라는 변수 때문입니다. 항상 큰 물고기를 먹는것이 반드시 최적해로 이끌어주지 않습니다. 따라서 상어가 먹는 경우의 수를 모두 고려해주기 위해 맵의 정보를 담고있는 Capture 구조체를 만듭니다.

   • 캡쳐된 상어의 정보 SharkInfo를 포함합니다.
   • 캡쳐된 현재 맵의 정보 map[4][4]를 포함합니다.
   • 현재까지 상어가 먹은 물고기 번호의 합 sum을 포함합니다.

3. 1번 물고기부터 본인이 향하는 방향으로 이동합니다.

   • 예상 도착 지점이 상어가 있는 위치거나, 맵을 벗어난다면 반시계 45도 회전합니다.
     • (다음 방향 번호) = (현재 방향 번호) % 8 + 1로 계산합니다.
   • 빈칸이거나 다른 물고기가 있는 칸이라면 위치를 바꿉니다.

4. 이제 상어가 움직일 차례입니다.

   • 4 x 4 맵이므로 상어가 먹을 수 있는 물고기는 최대 3마리 중 한 마리입니다.
   • 상어가 어떤 물고기를 먹었을 때의 상태를 Capture 배열에 저장합니다.

5. 상어가 더 이상 움직일 수 없을 때까지 과정 3, 4를 반복합니다.

   • 상어가 더 이상 움직일 수 없다면 answer = max(answer, 새로운 값); 을 해줍니다.

코드

#include <iostream>
#include <queue>
using namespace std;

typedef struct SharkInfo { int y, x, dir; } SharkInfo;
typedef struct Capture {
    SharkInfo shark;
    pair<int, int> map[4][4];
    int sum;
    explicit Capture(SharkInfo s, pair<int, int> oc[4][4], int sum) {
        this->shark.y = s.y; this->shark.x = s.x; this->shark.dir = s.dir;
        for (int y = 0; y < 4; ++y)
            for (int x = 0; x < 4; ++x)
                this->map[y][x] = oc[y][x];
        this->sum = sum;
    };
} Capture;

static int answer = 0;
static queue<Capture> captures;
static constexpr int moving[9][2] = {{0, 0}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};

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

void startMoveFishes() {
    Capture cap = captures.front(); captures.pop();
    cap.map[cap.shark.y][cap.shark.x].first = 0;	// 상어의 위치를 번호 '0'으로 만든다.

    for (int k = 1; k <= 16; ++k)
        for (int i = 0; i < 16; ++i) {
            int y = i / 4, x = i % 4;
            if (cap.map[y][x].first == k) {
                int ny = y + moving[cap.map[y][x].second][0];
                int nx = x + moving[cap.map[y][x].second][1];
                if (!isSafe(ny, nx) || (ny == cap.shark.y && nx == cap.shark.x))
                    for (int i = 1; i <= 8; ++i){	// 이동이 불가할경우 방향을 반시계방향으로 바꾼다.
                        cap.map[y][x].second = (cap.map[y][x].second % 8) + 1;
                        ny = y + moving[cap.map[y][x].second][0];
                        nx = x + moving[cap.map[y][x].second][1];
                        if (isSafe(ny, nx) && (ny != cap.shark.y || nx != cap.shark.x)) break;
                    }
                swap(cap.map[y][x], cap.map[ny][nx]);
                break;
            }
        }
    for (int i = 1; i <= 3; ++i) {	// 4x4 공간에서 상어는 최대 3칸 이동 가능하다.
        int ny = cap.shark.y + moving[cap.shark.dir][0] * i;
        int nx = cap.shark.x + moving[cap.shark.dir][1] * i;
        if (!isSafe(ny, nx)) break;
        if (cap.map[ny][nx].first == 0) continue;	// 빈칸이라면 굳이 갈 필요가 없다.
		
		// (ny, nx)칸에 있는 물고기를 먹었을 경우의 모든 정보를 captures에 저장하고 다른 경우의 수를 탐색한다.
        captures.push(Capture(SharkInfo{ny, nx, cap.map[ny][nx].second}, cap.map, cap.sum + cap.map[ny][nx].first));
    }
    answer = max(answer, cap.sum);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    pair<int, int> map[4][4];
    for (int y = 0; y < 4; ++y)
        for (int x = 0; x < 4; ++x)
            cin >> map[y][x].first >> map[y][x].second;
    
	// 시작 위치 정보 (상어정보, 현재 map 정보, 먹은 물고기 번호 합산)를 queue에 넣는다.
    captures.push(Capture(SharkInfo{0, 0, map[0][0].second}, map, map[0][0].first));
    // 상어가 더이상 움직일 수 없을 때까지 반복한다.
    while (!captures.empty()) startMoveFishes();
    cout << answer << '\n';
}

결과