문제 이해 단계
https://www.acmicpc.net/problem/16236
NxN 크기 맵에 상어와 물고기가 존재한다.
물고기와 상어는 각각 한 칸씩만 차지한다.
상어에는 크기, 물고기를 먹은 수의 개수 정보가 존재한다.
그리고 상어가 이동할 때는 아래의 규칙을 따른다.
1. 상어보다 크기가 작은 물고기만 먹을 수 있다.
2. 상어에게 제일 가까이 있는 물고기를 먹는다.
2-1 여러 마리가 있다면 가장 위쪽,
가장 위쪽이 여러 마리라면 가장 왼쪽 물고기를 먹는다.
3. 상어는 자신보다 큰 물고기가 있는 칸은 지나갈 수 없다.
(0인 칸이나, 크기가 같은 물고기가 있는 칸은 지나갈 수 있다.)
그리고 상어가 물고기를 먹으면 생기는 일은 아래와 같다.
1. 물고기를 먹은 수가 상어의 크기와 같아지면 상어의 크기가 커진다.
2. 상어의 크기가 커지기 때문에 먹을 수 있는 물고기가 더 많아진다.
아기 상어가 더 이상 먹을 수 있는 물고기가 없을 때 함수를 종료하고
이때까지 이동한 이동거리를 출력한다.
이때의 총 이동거리를 출력하는 문제이다.
문제 접근 단계
문제 자체에서 상어가 이동할 때의 규칙을 정의하는 것을 봐서,
높은 확률로 구현문제이다.
그리고 2차원 맵에서 상하좌우를 확인하고,
탐색하는 것을 보니 그래프 탐색을 이용할 수 있을 것 같다.
일단 규칙을 하나하나씩 쫓아가보자.
상어보다 작은 물고기, 가까운 물고기
상어가 타깃 물고기를 정할 때이다.
먹을 수 있는 가장 가까운 물고기를 정한다.
여기서 "먹을 수 있는" 이란 뜻은 상어보다 작은 물고기여야 한다.
그리고 "가까운 물고기"란 뜻은, 상어가 있는 좌표 기준으로
움직일 수 있는 곳으로의 이동거리가 최소여야 한다.
각각의 위치로의 최소 이동거리를 구하는 법은
BFS를 사용하여 쉽게 구할 수 있다.
이때, 그 사이에서 조건으로 상어의 크기와 물고기 크기에 대한
상관관계만 주면 상어보다 작은 물고기만 먹일 수 있다.
여기서 한 가지 주의해야 할 점은, 상어와 크기가 같은 물고기도
먹을 수 만 없을 뿐이지 지나갈 순 있다.
이런 식으로 BFS를 통해 현재 상어가 있는 위치에서,
각 물고기가 있는 좌표까지의 최소 거리를 모두 구한다.
그리고 그 거리가 가장 짧은 위치에 있는 물고기를
타깃으로 삼으면 된다.
물고기를 먹을 때
어떤 물고기를 먹을지 결정했다면,
이제 물고기를 먹을 때를 생각해 보자.
물고기를 먹을 때는 이동 → 먹기(성장) → 타깃 재설정 밖에 없다.
이동은 현재 상어의 위치에서 물고기가 있는 위치로 상어를 이동시키는 것이다.
이때 원래 상어가 있는 좌표는 0으로 바꿔주고,
물고기가 있는 좌표를 상어의 좌표인 9로 바꿔준다.
그리고 구해야 하는 것은 총 이동거리이기 때문에
이때의 이동한 거리를 따로 저장해둬야 한다.
먹기(성장)은 그냥 먹을 때 먹은 물고기수 + 1이 되는데
이때, 상어의 크기가 커지는지 체크하는 것이다.
타깃 재설정은 다음에 먹을 물고기가 남아있는지,
남아있다면 다음 타깃을 재설정하여 물고기 먹는 걸 반복하기 위한 것이다.
사실 여기까지가 해당 문제의 끝이다.
해당 문제를 로직적으로 보면 그렇게 어렵진 않다. 왜냐하면 구현 문제니까..
근데 구현문제니까 코드로 구현하기가 어렵다.
그러니까 코드로 구현해 보자..
문제 구현 단계
// 좌표 구조체
struct Point{
int x;
int y;
};
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
int N;// 맵 크기
int map[21][21]; // 맵
int dist[21][21] = {false,}; // 각 좌표의 거리
int shark = 2; // 상어의 크기
int eat = 0; // 먹은 물고기 수
// 가장 거리가 짧은 물고기 탐색
Point findFish(Point start){
int sx = start.x;
int sy = start.y;
bool v[N+1][N+1];
// 거리와 방문처리 초기화
fill(&v[0][0],&v[N][N+1],false);
fill(&dist[0][0],&dist[N][N+1],99999);
queue<Point> q;
q.push({sx,sy});
// 출발지 방문처리 및 거리 처리
v[sx][sy] = true;
dist[sx][sy] = 0;
map[sx][sy] = 0;
while(!q.empty()){
int x = q.front().x;
int y = q.front().y;
q.pop();
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 맵 밖으로 나가거나, 이미 방문했거나, 상어보다 큰 물고기거나,
// 하는 경우는 제외
if(nx < 1 || ny < 1 || nx > N || ny > N
|| v[nx][ny] || map[nx][ny] > shark) continue;
v[nx][ny] = true;
dist[nx][ny] = dist[x][y]+1; // 이동거리+1
q.push({nx,ny});
}
}
int min_dist = 99999; // 최소 이동거리
Point target; // 타겟 물고기
bool fail = true; // 실패 확인
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(map[i][j] != 0 && !(i == sx && j == sy)
&& map[i][j] < shark){
// 배열의 모든 숫자가 0이면 물고기가 없는 걸로 간주
if(dist[i][j] < min_dist) {
fail = false;
min_dist = dist[i][j];
target = {i,j};
}
}
}
}
if(fail) return {-1,-1};
else return target;
}상어가 먹을 물고기를 탐색하는 findFish함수이다.
매개변수로 현재 상어의 좌표를 받는다.
Point는 좌표를 직관적으로 받기 위해 만들어준 구조체이다.
나머지 전역변수들은 주석으로 달아놨기 때문에
알 수 있을 것이라 생각한다.
map과 대응되는 dist라는 2차원 변수를 둬서
각 좌표마다의 거리를 담아둔다.
그리고 방문을 체크하는 v배열 또한 만들어두고
이 함수를 호출할 때마다 매번 초기화해 준다.
초기화를 99999로 해주는 이유는 가장 최솟값을 구해야 하기 때문이다.
여기서 유의 깊게 봐야 할 것은
해당 칸에 있는 물고기가 shark의 크기보다 큰 경우이다.
이 경우엔 continue를 시켜 제외시켜 준다.
이렇게 함으로써, 상어보다 작거나 같은 물고기만을 지나갈 수 있게 하였다.
이렇게 만든 dist 배열 중 가장 작은 값을 가진 좌표를 타깃으로 삼아 반환시킨다.
만약 모든 값이 0이라는 것은 물고기가 없다는 것을 뜻하므로
-1을 반환하여 물고기가 없음을 알린다.
// 사냥할 때의 함수
Point hunting(Point start, Point fish){
// 원래 상어의 위치 초기화
map[start.x][start.y] = 0;
// 물고기 위치를 상어로 바꿈
map[fish.x][fish.y] = 9;
eat++; // 먹은 수 + 1
if(eat == shark){
// 먹은수 == 상어의 크기 일때
shark++;
eat = 0;
}
return {fish.x,fish.y}; // 이동한 위치 반환
}사냥할 때의 함수 hunting이다.
매개변수로 상어의 위치 start와 타깃 물고기의 위치 fish를 받는다.
간단하게 그냥 원래 상어의 위치를 0으로 초기화하고
물고기의 위치를 상어의 값인 9로 바꿔준다.
그리고 eat++로 먹은 수를 더해주고
이 값이 shark와 같아지면 shark++로 상어의 크기를 키워준다.
반환하는 것은 이동한 위치를 반환해서 나중에 start의 위치를 바꿔줄 때 쓴다.
여기까지 핵심 함수 설명 끝이고 아래에 전체 함수에 대해 올리고 포스팅을 마치겠다.
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
// 좌표 구조체
struct Point{
int x;
int y;
};
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
int N;// 맵 크기
int map[21][21]; // 맵
int dist[21][21] = {false,}; // 각 좌표의 거리
int shark = 2; // 상어의 크기
int eat = 0; // 먹은 물고기 수
// 가장 거리가 짧은 물고기 탐색
Point findFish(Point start){
int sx = start.x;
int sy = start.y;
bool v[N+1][N+1];
// 거리와 방문처리 초기화
fill(&v[0][0],&v[N][N+1],false);
fill(&dist[0][0],&dist[N][N+1],99999);
queue<Point> q;
q.push({sx,sy});
// 출발지 방문처리 및 거리 처리
v[sx][sy] = true;
dist[sx][sy] = 0;
map[sx][sy] = 0;
while(!q.empty()){
int x = q.front().x;
int y = q.front().y;
q.pop();
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 맵 밖으로 나가거나, 이미 방문했거나, 상어보다 큰 물고기거나,
// 하는 경우는 제외
if(nx < 1 || ny < 1 || nx > N || ny > N
|| v[nx][ny] || map[nx][ny] > shark) continue;
v[nx][ny] = true;
dist[nx][ny] = dist[x][y]+1; // 이동거리+1
q.push({nx,ny});
}
}
int min_dist = 99999; // 최소 이동거리
Point target; // 타겟 물고기
bool fail = true; // 실패 확인
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(map[i][j] != 0 && !(i == sx && j == sy)
&& map[i][j] < shark){
// 배열의 모든 숫자가 0이면 물고기가 없는 걸로 간주
if(dist[i][j] < min_dist) {
fail = false;
min_dist = dist[i][j];
target = {i,j};
}
}
}
}
if(fail) return {-1,-1};
else return target;
}
// 사냥할 때의 함수
Point hunting(Point start, Point fish){
// 원래 상어의 위치 초기화
map[start.x][start.y] = 0;
// 물고기 위치를 상어로 바꿈
map[fish.x][fish.y] = 9;
eat++; // 먹은 수 + 1
if(eat == shark){
// 먹은수 == 상어의 크기 일때
shark++;
eat = 0;
}
return {fish.x,fish.y}; // 이동한 위치 반환
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N;
Point start;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
cin >> map[i][j];
if(map[i][j] == 9) start = {i,j};
}
}
int ans = 0;
while(true){
Point fish = findFish(start);
if(fish.x == -1) break;
ans += dist[fish.x][fish.y];
Point next = hunting(start,fish);
start = next;
}
cout << ans;
}시행착오
골드 3 치고는 직관적이고 쉬웠던 문제 같다.
아니면 그래프 탐색 쪽은 자신 있어서 그런지 실수 없지 잘 해결한 것 같다.
문제가 이런 식으로만 나왔으면 좋겠지만 그렇지는 않겠지.
아무튼 이번에는 한 2시간? 안에 푼 것 같아서 뿌듯하다.
앞으로도 이런 식으로 열심히 풀어봐야지.