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

백준 19236번 청소년 상어 문제이다.

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

4*4 공간의 16마리의 물고기가 번호와 이동 방향이 함께 주어진다.

물고기는 다른 물고기가 있거나 비어있는 공간으로 이동이 가능하다. 상어가 있어나 경계의 바깥으로는 이동할 수 없다. 이동할 수 없는 경우 반시계 방향으로 45 degree 씩 움직이면서 이동 가능한 공간을 탐색한다.
물고기는 낮은 번호부터 순차적으로 이동한다.

상어는 항상 0,0에 있는 물고기를 잡아 먹으면서 이 공간으로 들어오고, 상어의 다음 방향은 잡아 먹은 물고기의 방향과 같아진다.
상어는 비어있는 공간으로 이동할 수 없고, 경계의 바깥으로도 이동할 수 없다.
상어가 이동했을 때,
이 문제에서 중요한 점은 dfs의 설계이고, dfs의 중요한 점은 재귀함수와 재귀의 끝에서 함수가 return 되었을 때, 다시 이전 상태로 복귀하는 것이다.

헷갈렸던 부분

헷갈린건 아니고... 나는 낮은 번호의 물고기부터 움직인다고 해서 순차배열을 기본으로 지원하는 map 타입을 사용했는데, 정답 이후에 다른 사람 풀이를 보니 넣을 때부터 배열을 만들어서 번호에 맞춘 인덱스에 집어 넣었다. map에 넣는 것보다 배열이 더 빠를 것 같은데, 연산결과는 모두 0ms여서 더 테스트 해보지 않았다.

입력

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

출력

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

문제분석

핵심이 되는 파트는

1. 물고기는 낮은번호부터 움직인다 -> map 또는 vector의 index 구분으로 입력과 동시에 순서 지정 (들어오는 순서는 랜덤)
2. 물고기 이동 시뮬레이션
3. 상어가 먹을 수 있는 물고기 번호의 합의 최댓값 출력 -> 선택에 따른 dfs 분기 (한 칸 움직일 때와 두 칸 움직일 때 등등)
   라고 생각한다.

해결과정

1. 이번에는 입력 받기전에 struct를 사용해서 물고기와 상어를 정의하고 공간 환경을 만들었다.
   다른 사람들의 풀이과 비교하자면, fish에 alive 상태를 넣는 대신 id가 0인 것을 죽은 상태로, -1을 상어의 위치로 생각했다
   공간을 fish의 이중 벡터로 설정했다.

// main함수보다 위에서 정의함
struct fish {
  int id;
  int dir;
  int x;
  int y;
};

struct shark {
  int dir;
  int x;
  int y;
};
vector<vector<fish>> origin_pond;
map<int, fish> origin_fishes;

2. 입력을 받는다. map 타입을 사용했기 때문에 기본적으로 key 값을 기준으로 오름차순 정렬된다.

int a, b;
for (int i = 0; 4 > i; ++i) {
  vector<fish> tmp;
  for (int j = 0; 4 > j; ++j) {
    cin >> a;
    cin >> b;
    tmp.emplace_back(fish{a, b, i, j});
    origin_fishes.insert(pair<int, fish>(a, fish{a, b, i, j}));
  }
  origin_pond.emplace_back(tmp);
}

3. 상어의 시작 위치는 고정이므로 일단 넣어준다.

origin_fishes.erase(origin_pond[0][0].id);
answer += origin_pond[0][0].id;
shark cur_shark;
cur_shark.dir = origin_pond[0][0].dir;
cur_shark.x = origin_pond[0][0].x;
cur_shark.y = origin_pond[0][0].y;
origin_pond[0][0].id = -1;

4. 물고기들의 이동을 표현하는 함수를 만들어야 한다. move_fish 라는 이름으로 정의했다. 더불어, 외부/내부를 검증 함수는 따로 만들면 이해가 쉬울 것 같아서 같이 만들어줬다.
   아, 참고로 &&과 &, ||과 |는 다른 연산자이다. && 또는 ||는 앞쪽에서 전체 결과가 결정나면 뒤를 검증하지 않고 return해서 비교적 빠르게 비교를 수행할 수 있다.
   우선, map을 활용한 fishes 변수를 for (auto& : )를 사용해서 순환한다. pond나 fishes는 변경될 수 있으므로 const &가 아닌 &로 사용한다.
   물고기의 방향을 기준으로 다음 이동할 위치가 외부인지, 상어가 존재하는 위치인지를 검증한다. 조건에 해당하면 방향을 변경해준다. 입력받을 때, 방향을 1번부터 받았으므로, 사용하지 않지만 dx dy 함수의 인덱스 0에 아무 값이나 넣어주면 코드 이해가 쉽다. dir 9는 존재하지 않기 때문에 9에 도달하면 1로 변경해준다.
   물고기는 빈 공간 또는 다른 물고기가 있는 (상어가 아닌) 위치로 이동할 수 있다. 두 경우는 서로 다른 경우이므로 나눠준다. 특히, fishes에 있는 값의 처리 부분이 다르기 때문에 유의해야한다.

const vector<int> dx = {0, -1, -1, 0, 1, 1, 1, 0, -1};
const vector<int> dy = {0, 0, -1, -1, -1, 0, 1, 1, 1};

bool check_outer(int x, int y) {
  return (x < 0 || y < 0 || x > 3 || y > 3);
}

void move_fish(vector<vector<fish>>& pond, map<int, fish>& fishes) {
  // map으로 sort
  for (auto& fish : fishes) {
    int dir = fish.second.dir;
    for (int i = 1; dx.size() > i; ++i) {
      int nx = fish.second.x + dx[dir];
      int ny = fish.second.y + dy[dir];
      if (check_outer(nx, ny) == true || pond[nx][ny].id == -1 /*shark id*/) {
        // case of cant move
        ++dir;
        if (dir == 9) {
          dir = 1;
        }
        // dir = (dir + i) % 8;
      } else {
        int cur_x = fish.second.x;
        int cur_y = fish.second.y;
        fish.second.dir = dir;
        // fishes update
        if (pond[nx][ny].id == 0) {
          // vacant
          pond[cur_x][cur_y].id = 0;
          pond[cur_x][cur_y].dir = pond[nx][ny].dir;
          pond[nx][ny].id = fish.second.id;
          pond[nx][ny].dir = dir;
          fish.second.x = nx;
          fish.second.y = ny;
        } else {
          swap(fishes[pond[nx][ny].id].x, fish.second.x);
          swap(fishes[pond[nx][ny].id].y, fish.second.y);
          // pond update
          pond[cur_x][cur_y].dir = dir;
          swap(pond[cur_x][cur_y].id, pond[nx][ny].id);
          swap(pond[cur_x][cur_y].dir, pond[nx][ny].dir);
        }
        break;
      }
    }
  }
}

5. 중요한 함수이다. 상어가 움직이는 것을 나타낸다. DFS를 작성할 때는 항상 이전 상태로의 복귀 부분을 잘 설계해야한다.
   이 문제에서는 이전 상태의 공간과, 물고기 목록이 있는 fishes, 상어의 상태(위치)를 되돌려 줘야한다.

void eat(vector<vector<fish>>& pond, map<int, fish>& fishes, shark& cur_shark, int ans) {
  vector<vector<fish>> tmp_pond = pond;
  map<int, fish> tmp_fishes = fishes;
  shark tmp_shark = cur_shark;
  move_fish(tmp_pond, tmp_fishes);
  answer = max(answer, ans);
  tmp_pond[tmp_shark.x][tmp_shark.y].id = 0;  // shark leave

  for (int i = 1; 4 > i; ++i) {
    int tmp_x = tmp_shark.x + dx[tmp_shark.dir] * i;
    int tmp_y = tmp_shark.y + dy[tmp_shark.dir] * i;
    if (check_outer(tmp_x, tmp_y) == true) {
      // cant move
      answer = max(answer, ans);
      return;
    } else if (tmp_pond[tmp_x][tmp_y].id == 0) {
      continue;
    } else {
      int id = tmp_pond[tmp_x][tmp_y].id;
      ans += id;
      fish deleted_fish = tmp_pond[tmp_x][tmp_y];
      tmp_shark = shark{tmp_pond[tmp_x][tmp_y].dir, tmp_x, tmp_y};
      tmp_fishes.erase(deleted_fish.id);
      tmp_pond[tmp_x][tmp_y].id = -1;  // shark appear
      eat(tmp_pond, tmp_fishes, tmp_shark, ans);

      tmp_pond[tmp_x][tmp_y].id = id;
      tmp_shark = cur_shark;
      tmp_fishes[deleted_fish.id] = deleted_fish;
      ans -= id;
    }
  }
  tmp_pond = pond;
}

6. 결과이다.
   다만, 정답을 맞춘 사람들이 거의 대부분 0ms 여서 얼마나 빠른지는 명시적으로 확인하기 어려웠다