백준 16236 아기상어 C++ 풀이

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

 

 

오랜만에 백준 문제를 풀었습니다. 저는 BFS를 이용하여 AC를 받았고 minimum_distance의 초깃값을 20*20인 400보다 큰 값으로 설정해야 하는데 습관적으로 100이라고 하는 바람에 WA를 3번이나 받았습니다.   

 

메인 함수의 로직은 아래와 같습니다.

아기 상어의 먹잇감을 찾는 find_prey() 함수를 구현하여 먹이를 못 찾을 때까지 무한루프를 돌면서 먹이를 찾습니다.

while(true){
        if(find_prey(s)){
            continue;
        }else{
            break;
        }
 }
 cout <<ans<<endl;

 

find_prey 함수는 shark 구조체의 포인터 변수를 입력받아 이 상어가 먹이를 찾을 수 있는지 없는지를 판단하는 함수입니다. 먹이를 찾게된다면, 전역변수로 선언된 ans의 값을 다음 먹이까지의 최단거리만큼 증가시켜줍니다.

 

최단 거리를 구하는 과정은 BFS를 통해 현재 상어의 위치에서 상하 좌우로 이동해보면서 상어는 상어의 크기보다 작거나 같은 상어 또는 빈칸으로만 이동할 수 있다는 조건에 부합할 때만 큐에 넣고 dist[][]배열에 최단거리를 저장합니다.

q.push({s.y, s.x});
dist[s.y][s.x] = 0;
//BFS find shortest path
while(!q.empty()){
      int y = q.front().first;
      int x = q.front().second;
      q.pop();
      if(arr[y][x] !=9 && arr[y][x] !=0  && arr[y][x] <s.size){continue;}
      for(int i=0; i<4; i++){
          int ny = y+dy[i];
          int nx = x+dx[i];
          // 다음 위치가 범위를 벗어나지 않고, 이전에 방문하지 않았으며, 자신의 크기보다 작거나 같은 크기의 상어이면 이동
          if(ny>=0 && ny<n && nx>=0 && nx<n && dist[ny][nx]==-1 &&arr[ny][nx]<=s.size ){
              dist[ny][nx] = dist[y][x]+1;
              q.push({ny, nx});
          }
       }
 }

 

이 때 최단거리를 통해 방문한 모든 상어 중 가장 가까우면서, 가장 위에 있으면서, 가장 왼쪽에 있는 상어를 잡아먹어야 한다는 조건이 있기 때문에 n-1행부터 0행까지, n-1열부터 0열까지 거꾸로 순회하며 가장 최단거리의 상어를 찾고 상어를 먹으면서 구조체의 속성값을 업데이트 해줍니다. 그리고 먹이를 찾을 수 있으므로 true값을 리턴해줍니다.

 

만약 m_dist가 초깃값 그대로 401이라면 먹이를 찾지 못하였음을 의미하기 때문에 false를 리턴해줍니다.

    // find minimum y, x, dist 
    int my = 100;
    int mx = 100;
    int m_dist = 401;
    for(int i=n-1; i>=0; i--){
        for(int j=n-1; j>=0; j--){
            if(arr[i][j]!=0 && arr[i][j] !=9&& arr[i][j]<s.size && dist[i][j] != -1 && dist[i][j]<=m_dist){
                m_dist = dist[i][j];
                my = i;
                mx = j;
            }
        }
    }
    if(m_dist == 401){
        return false;
    }else{
        arr[s.y][s.x] =0; 
        s.y = my;
        s.x = mx;
        s.eat++;
        if(s.eat ==  s.size){
            s.eat = 0;
            s.size++;
        }
        arr[my][mx] = 9;
        ans+= dist[my][mx];
        return true;
    }

 

전체 소스코드는 아래와 같습니다.

 

 

전체 소스코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int arr[21][21];
int ans = 0;
int n;
struct shark{
    int y;
    int x;
    int size;
    int eat;
};
int dist[21][21];
int dy[4] = {1,-1,0,0};
int dx[4] = {0,0,-1,1};
bool find_prey(shark& s){
    queue<pair<int, int> > q;
    // initialize dist 
    for(int i=0; i<21; i++)
        for(int j=0; j<21; j++)
            dist[i][j] = -1;
    q.push({s.y, s.x});
    dist[s.y][s.x] = 0;
    //BFS find shortest path
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        if(arr[y][x] !=9 && arr[y][x] !=0  && arr[y][x] <s.size){continue;}
        for(int i=0; i<4; i++){
            int ny = y+dy[i];
            int nx = x+dx[i];
            if(ny>=0 && ny<n && nx>=0 && nx<n && dist[ny][nx]==-1 &&arr[ny][nx]<=s.size ){
                dist[ny][nx] = dist[y][x]+1;
                q.push({ny, nx});
            }
        }
    }
    // find minimum y, x, dist 
    int my = 100;
    int mx = 100;
    int m_dist = 401;
    for(int i=n-1; i>=0; i--){
        for(int j=n-1; j>=0; j--){
            if(arr[i][j]!=0 && arr[i][j] !=9&& arr[i][j]<s.size && dist[i][j] != -1 && dist[i][j]<=m_dist){
                m_dist = dist[i][j];
                my = i;
                mx = j;
            }
        }
    }
    if(m_dist == 401){
        return false;
    }else{
        arr[s.y][s.x] =0; 
        s.y = my;
        s.x = mx;
        s.eat++;
        if(s.eat ==  s.size){
            s.eat = 0;
            s.size++;
        }
        arr[my][mx] = 9;
        ans+= dist[my][mx];
        return true;
    }
}
int main(){
    shark s;
    cin>>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>> arr[i][j];
            if(arr[i][j] == 9){
                s.y = i;
                s.x = j;
                s.size = 2;
                s.eat = 0;
            }
        }
    }
    while(true){
        if(find_prey(s)){
            continue;
        }else{
            break;
        }
    }
    cout <<ans<<endl;
    return 0;
}

 

이상으로 백준 16236 아기상어 포스팅을 마치겠습니다. 감사합니다.