백준 17086번 아기 상어 2 (C++)

문제 링크 : https://www.acmicpc.net/problem/17086

17086번: 아기 상어 2

문제 요약

 

1. 안전거리는 어느 칸 하나와 가장 가까운 아기 상어와의 거리입니다.

2. 두 칸 사이의 거리는 8방향(대각선 포함)으로 이동하는 최단거리 입니다.

3. 안전거리가 가장 큰 값을 구하세요.

 

핵심 포인트

 

안전거리의 뜻을 잘 이해해야합니다.

빈 칸은 무조건 한 개 이상이 주어지므로, 결국 주어진 모든 빈칸에서 가장 가까운 아기 상어와의 거리(=안전 거리) 중 최대값을 구해야합니다.

 

문제 풀이

 

1. 필요한 변수들을 선언하고 값을 입력 받습니다.

배열에서 값이 0인 구역에 한해 bfs를 진행합니다.

cin >> n >> m;
    vector<vector<int>> v(n,vector<int>(m,0));
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++) cin >> v[i][j];
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(v[i][j]==0) bfs(v,i,j);
        }
    }

 

2. 다음은 bfs코드 입니다.

struct shark{
    int yy, xx;
    int move;
};

void bfs(vector<vector<int>> &v, int a, int b){
    vector<vector<bool>> ch(n,vector<bool>(m,false)); // 1
    queue<shark> q; // 2
    q.push({a,b,0});
    ch[a][b] = true; // 3
    while(!q.empty()){
        y = q.front().yy; // 4
        x = q.front().xx;
        mm = q.front().move;
        q.pop();
        for(int i=0; i<8; i++){ // 5
            ny = y+my[i];
            nx = x+mx[i];
            if(ny<0||ny>=n||nx<0||nx>=m||ch[ny][nx]) continue; // 6
            ch[ny][nx] = true; // 7
            if(v[ny][nx]==1){ // 8
                if(mm+1>ans) ans = mm+1; 
                return;
            }
            q.push({ny,nx,mm+1}); // 9
        }
    }
    return;
}

(1) 방문여부를 표시할 벡터를 만듭니다.

(2) 상어 구조체의 큐를 만들고 현재 위치를 삽입합니다.

(3) 현재 위치를 방문표시 합니다.

(4) 현재 위치를 변수에 저장합니다.

(5) 8방위로 for문을 돌립니다.

(6) 만약 새로운 위치가 범위를 초과하거나 이미 방문한 위치라면, continue를 합니다.

(7) 새로운 위치를 방문표시 합니다.

(8) 새로운 위치가 1이라면, 가장 가까운 상어와의 거리, 즉, 안전 거리가 됩니다. 해당 안전 거리의 값이 더 크다면 새로이 값을 갱신합니다. 그리고 return 하여 bfs 함수를 빠져나옵니다.

(9) 그렇지 않을 경우 큐에 새로운 위치와 누적 움직임 횟수를 저장합니다.

 

3. 모든 위치를 다 방문하고 안전 거리를 구했으면, 정답을 출력합니다.

 

#include <string>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n,m,y,x,mm,ny,nx,my[]={-1,-1,-1,0,0,1,1,1},mx[]={-1,0,1,-1,1,-1,0,1},ans=0;
struct shark{
    int yy, xx;
    int move;
};

void bfs(vector<vector<int>> &v, int a, int b){
    vector<vector<bool>> ch(n,vector<bool>(m,false));
    queue<shark> q;
    q.push({a,b,0});
    ch[a][b] = true;
    while(!q.empty()){
        y = q.front().yy;
        x = q.front().xx;
        mm = q.front().move;
        q.pop();
        for(int i=0; i<8; i++){
            ny = y+my[i];
            nx = x+mx[i];
            if(ny<0||ny>=n||nx<0||nx>=m||ch[ny][nx]) continue;
            ch[ny][nx] = true;
            if(v[ny][nx]==1){
                if(mm+1>ans) ans = mm+1; 
                return;
            }
            q.push({ny,nx,mm+1});
        }
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    vector<vector<int>> v(n,vector<int>(m,0));
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++) cin >> v[i][j];
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(v[i][j]==0) bfs(v,i,j);
        }
    }
    cout << ans << "\n";
}