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

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

17086번: 아기 상어 2

브루트포스와 BFS가 합쳐진 문제였습니다.

map이 주어졌을때, 상어와 가장 멀리 떨어진 위치를 찾는 곳입니다.

주어질 수 있는 map의 크기가 크지 않기 때문에 모든 곳에서 상어와 떨어진 거리를 확인해보면 되는 문제입니다.

 

for문을 통해, map의 값이 0인 모든 곳에서 8방향 탐색을 시작해 1과 만나면 바로 탈출해주면 됩니다.

이때의 이동거리를 계속 비교해서 가장 큰 거리를 출력해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <math.h>
#include <cstdio>
#define P pair<int, int>
#define PP pair<P, int>
#define F first
#define S second

using namespace std;

int N, M;
int map[51][51];
int check[51][51];
int dx[8] = {0,1,0,-1,1,-1,1,-1};
int dy[8] = {1,0,-1,0,1,-1,-1,1};

int bfs(int X, int Y){
    memset(check, 0, sizeof(check));
    queue<PP> q;
    check[X][Y] = 1;
    q.push({{X,Y}, 0});
    while(!q.empty()){
        int x = q.front().F.F;
        int y = q.front().F.S;
        int cnt = q.front().S;
        q.pop();
        for(int i = 0; i < 8; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
                if(map[xx][yy] == 1) return cnt + 1;
                if(check[xx][yy] == 0 && map[xx][yy] == 0){
                    q.push({{xx,yy},cnt+1});
                    check[xx][yy] = 1;
                }
            }
        }
    }
}

void solve(){
    int dis = 0;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(map[i][j] == 0){
                if(dis < bfs(i,j)) dis = bfs(i,j); 
            }
        }
    }
    cout << dis;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> map[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요!