[알고리즘] 백준 16236 아기상어

도입

2020년 상반기 삼성전자 기출문제인 백준(#16236) 아기상어 문제를 풀어봅시다!

탐색 및 시뮬레이션 문제입니다. 처음 보기에 문제가 길고 복잡해서 어려워 보일 수 있습니다. 하지만 먼저 문제를 잘 이해했는지 꼭 확인해보고 주어진 조건을 확인해가면서 코딩하다 보면 어느새 정답의 코드를 도출해낼 수 있을 것입니다. - solved.ac 골드 5

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야 하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

Code

우선 전체적인 논리를 살펴봅시다.

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int N;
  cin >> N;
  vii ocean(N, vi(N, 0));
  Shark baby = placeFishTo(ocean, N);

  int time = INF;
  int total = 0;

  while (time) {
    vii mDist = calculate(ocean, N, baby);
    time = solve(ocean, mDist, N, baby);
    total += time;
  }

  cout << total << '\n';

  return 0;
}

1. 입력

입력으로 주어지는 물고기들의 위치를 Shark baby = placeFishTo(ocean, N); 를 통해 맵에 입력받습니다. 이때 아기상어의 위치와 크기는 객체로 만들어 맵(ocean)과 분리합니다.

Shark 객체는 다음과 같은 구조체로 정의되어있습니다.

struct Shark {
  int r;    // 행을 의미합니다.
  int c;    // 열을 의미합니다.
  int size;    // 상어의 크기 혹은 상어와의 거리를 기록합니다.
  Shark(int r, int c, int s) {
    this->r = r;
    this->c = c;
    this->size = s;
  }
};

 

입력 소스는 다음과 같습니다.

Shark placeFishTo(vii &ocean, int N) {
  Shark baby(0, 0, 2);

  for (int r=0; r<N; r++) {
    for (int c=0; c<N; c++) {
      cin >> ocean[r][c];
      if (ocean[r][c] == 9) {
        baby.r = r;
        baby.c = c;
        ocean[r][c] = 0;
      }
    }
  }

  return baby;
}

 

아기상어의 크기는 2이고 입력 행렬에서 아기상어의 위치가 9로 표시된다는 조건을 활용하여 아기상어 객체를 생성하고 맵을 생성 합니다.

2. BFS 탐색

vii mDist = calculate(ocean, N, baby); 를 통해 아기상어의 현재 위치에서 방문할 수 있는 좌표까지의 최단거리를 BFS를 활용하여 계산합니다.

vii calculate(vii &ocean, int N, Shark &baby) {
  vii visited(N, vi(N, 0));
  vii mdist(N, vi(N, -1));
  qs q;

  q.push(baby);
  visited[baby.r][baby.c] = true;
  mdist[baby.r][baby.c] = 0;

  while (!q.empty()) {
    Shark x = q.front(); q.pop();

    vs dir = {
      Shark(x.r-1, x.c, x.size), Shark(x.r, x.c-1, x.size),
      Shark(x.r+1, x.c, x.size), Shark(x.r, x.c+1, x.size)
    };

    for (Shark each : dir) {
      if (each.r<0 || each.c<0) continue;
      if (each.r>=N || each.c>=N) continue;
      if (visited[each.r][each.c]) continue;
      if (ocean[each.r][each.c] > baby.size) {
        visited[each.r][each.c] = true;
        continue;
      }
      mdist[each.r][each.c] = mdist[x.r][x.c] + 1;
      visited[each.r][each.c] = true;
      q.push(each);
    }
  }

  return mdist;
}

 

우선 아기상어가 맵의 모든 칸에 방문할 수 없다고 가정하고 vii mdist(N, vi(N, -1)); 로 초기화합니다. 아기 상어의 현재 위치와 크기가 기록되어있는 baby 객체를 큐에 넣습니다. 아기상어가 상하좌우로 인접한 한 칸씩 이동할 수 있다는 조건을 활용하여 인접한 좌표로 이동한 경우의 상어 객체를 벡터에 넣어둔 후 순회하면서 다음과 같은 사항을 확인합니다.

1. 주어진 좌표가 맵의 범위 안에 존재하는가?
2. 주어진 좌표가 이미 방문한 곳인가?
3. 주어진 좌표에 존재하는 상어가 아기상어보다 큰가?

아기상어가 맵 밖으로 나가는 것은 불가능하며, 아기상어가 가려고 했던 좌표가 이미 방문한 곳이었다면 최단거리가 아닙니다.

"아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다."

문제에서 주어진 위 조건에 따라서 주어진 좌표에 존재하는 상어가 아기 상어보다 크면 지나갈 수 없으며 같거나 작다면 지나갈 수 있으므로 거리를 계산하게 됩니다. 위 조건에 걸리지 않으면 모든 좌표를 방문할 때까지 거리를 1씩 누적해가며 최단거리를 탐색합니다. 이후 갱신된 최단거리 벡터를 리턴합니다.

3. 시뮬레이션

time = solve(ocean, mDist, N, baby); 을 통해 주어진 맵에서 먹을 수 있는 상어를 순서에 알맞게 먹고 아기 상어의 몸집을 키웁니다. 먹을 수 있는 상어가 있다면 그 상어를 먹기 위해 이동하는 거리를 리턴하고 먹을 수 있는 상어가 없으면 0을 리턴합니다.

int solve(vii &ocean, vii &mdist, int N, Shark &baby) {
  pqs sharks;

  for (int i=0; i<N; i++) {
    for (int j=0; j<N; j++) {
      if (mdist[i][j]>0 && 1<=ocean[i][j] && ocean[i][j]<=baby.size) {
        Shark shark(i, j, mdist[i][j]);
        sharks.push(shark);
      }
    }
  }

  bool canEatFish = false;
  Shark minShark(0, 0, 0);

  while (!sharks.empty()) {
    Shark shark = sharks.top();
    sharks.pop();
    if (baby.size > ocean[shark.r][shark.c]) {
      canEatFish = true;
      minShark = shark;
      break;
    }
  }

  if (canEatFish) {
    baby.r = minShark.r;
    baby.c = minShark.c;

    if (baby.size > ocean[baby.r][baby.c]) {
      ate++;
      ocean[baby.r][baby.c] = 0;
    }

    if (ate >= baby.size) {
      baby.size++;
      ate = 0;
    }
  }

  return minShark.size;
}

 

맴에서 상어가 있는 장소 중 아기상어가 지나갈 수 있는 장소를 가중치-큐에 담습니다. 가중치-큐에서 지나갈 수 있는 상어들이 정렬되는 원리는 다음과 같습니다.

bool operator>(Shark a, Shark b) {
  if (a.size > b.size) {
    return true;
  } else if (a.size == b.size && a.r > b.r) {
    return true;
  } else if (a.size == b.size && a.r == b.r && a.c > b.c) {
    return true;
  }

  return false;
}

 

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다.
먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기상어가 어느 좌표를 지나갈 수 있는지, 어느 상어를 먹을 수 있는지 혹은 먹으려는 상어의 순서를 고려할 때 위와 같은 문제의 조건을 활용합니다. 최우선적으로는 아기상어가 방문할 수 있는 지역중에서 상어가 존재하는 곳을 살펴봅니다. 아기상어와 어느 좌표의 상어와의 크기를 비교했을때 같거나 작은 경우가 아기상어가 먹을 수 있는 상어들의 리스트를 작성하는데 필요한 조건입니다. 아기상어는 가장 가까운 거리에 있는 상어를 먹으러 가지만 그러한 물고기가 여러 마리라면 가장 위쪽 행에 있는 상어를 우선적으로 먹고, 그마저도 같다면 가장 왼쪽 열에 있는 상어를 먹으러 갈 수 있도록 연산자 오버로딩을 통해 가중치-큐에서 정렬되게 만듭니다.

아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.
아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다.

가중치 큐에 담긴 상어들 중에는 아기 상어와 크기 같아서 먹을 수 없는 상어들도 있고 크기가 작아서 먹을 수 있는 상어도 섞여있습니다. 즉, 특정한 경우엔 맵에서 아기상어와 크기가 같은 상어들만 남는다면 알고리즘의 유한성을 만족시킬 수 없는 상황이 발생할 수 있다는 점입니다. 이러한 문제점을 해결하기 위해 도입된 개념이 bool canEatFish = false; 입니다. 아기상어가 지나갈 수 있는 상어가 담긴 가중치-큐에서 상어를 하나씩 꺼내보면서 아기상어가 먹을 수 있는지 확인합니다. 만약 아기상어가 먹을 수 있는 상어가 처음으로 등장한다면 그 상어는 아기상어가 먹을 수 있는 상어들 중에 최우선적으로 먹어야 하는 상어가 되며 minShark 객체로 저장됩니다. 또한 canEatFish 변수가 참값으로 바뀌어 아기상어가 성장할 수 있는지 고려할 수 있게됩니다. 아기상어가 몇 마리를 먹었는지는 전역 변수인 ate 에 기록되고 아기상어의 현재 크기와 같은 수의 물고기를 먹을 때마다 1씩 증가시키게 됩니다.

정리하자면 canEatFish가 참이 되어서 minShark에 새로운 좌표, 아기상어와의 최단거리 값이 담기게 된다면 최단거리를 리턴 하지만 canEatFish가 거짓이어서 먹을 수 있는 상어가 없다면 minShark의 기본 거리 값인 0이 리턴되고 main 함수에 이 값을 참조하여 반복문을 돌리는 부분이 동작하게 됩니다.

4. 출력

아기 상어가 먹을 수 있는 모든 상어를 잡아먹을 때까지 이동하는 거리를 int total = 0; 에 누적하고 cout << total << '\n'; 결과물을 출력합니다.

교훈

문제를 잘 읽고 이해하는 것도 능력입니다. ('20.08.23)

전체 코드

#include <bits/stdc++.h>
using namespace std;

struct Shark {
  int r;
  int c;
  int size;
  Shark(int r, int c, int s) {
    this->r = r;
    this->c = c;
    this->size = s;
  }
};

bool operator>(Shark a, Shark b) {
  if (a.size > b.size) {
    return true;
  } else if (a.size == b.size && a.r > b.r) {
    return true;
  } else if (a.size == b.size && a.r == b.r && a.c > b.c) {
    return true;
  }

  return false;
}

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<Shark> vs;
typedef queue<Shark> qs;
typedef priority_queue<Shark, vs, greater<Shark> > pqs;

const int INF = 987654321;
int ate = 0;

vii calculate(vii &ocean, int N, Shark &baby) {
  vii visited(N, vi(N, 0));
  vii mdist(N, vi(N, -1));
  qs q;

  q.push(baby);
  visited[baby.r][baby.c] = true;
  mdist[baby.r][baby.c] = 0;

  while (!q.empty()) {
    Shark x = q.front(); q.pop();
    
    vs dir = {
      Shark(x.r-1, x.c, x.size), Shark(x.r, x.c-1, x.size),
      Shark(x.r+1, x.c, x.size), Shark(x.r, x.c+1, x.size)
    };

    for (Shark each : dir) {
      if (each.r<0 || each.c<0) continue;
      if (each.r>=N || each.c>=N) continue;
      if (visited[each.r][each.c]) continue;
      if (ocean[each.r][each.c] > baby.size) {
        visited[each.r][each.c] = true;
        continue;
      }
      mdist[each.r][each.c] = mdist[x.r][x.c] + 1;
      visited[each.r][each.c] = true;
      q.push(each);
    }
  }

  return mdist;
}

int solve(vii &ocean, vii &mdist, int N, Shark &baby) {
  pqs sharks;

  for (int i=0; i<N; i++) {
    for (int j=0; j<N; j++) {
      if (mdist[i][j]>0 && 1<=ocean[i][j] && ocean[i][j]<=baby.size) {
        Shark shark(i, j, mdist[i][j]);
        sharks.push(shark);
      }
    }
  }

  bool canEatFish = false;
  Shark minShark(0, 0, 0);

  while (!sharks.empty()) {
    Shark shark = sharks.top();
    sharks.pop();
    if (baby.size > ocean[shark.r][shark.c]) {
      canEatFish = true;
      minShark = shark;
      break;
    }
  }

  if (canEatFish) {
    baby.r = minShark.r;
    baby.c = minShark.c;

    if (baby.size > ocean[baby.r][baby.c]) {
      ate++;
      ocean[baby.r][baby.c] = 0;
    }

    if (ate >= baby.size) {
      baby.size++;
      ate = 0;
    }
  }

  return minShark.size;
}

Shark placeFishTo(vii &ocean, int N) {
  Shark baby(0, 0, 2);

  for (int r=0; r<N; r++) {
    for (int c=0; c<N; c++) {
      cin >> ocean[r][c];
      if (ocean[r][c] == 9) {
        baby.r = r;
        baby.c = c;
        ocean[r][c] = 0;
      }
    }
  }

  return baby;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int N;
  cin >> N;
  vii ocean(N, vi(N, 0));
  Shark baby = placeFishTo(ocean, N);

  int time = INF;
  int total = 0;
  
  while (time) {
    vii mDist = calculate(ocean, N, baby);
    time = solve(ocean, mDist, N, baby);
    total += time;
  }
  
  cout << total << '\n';
  
  return 0;
}