[C++] 백준 문제풀이 (Bruteforcing) 17086번 아기 상어 2

코딩준우 2023. 7. 1. 00:36

https://www.acmicpc.net/problem/17086

17086번: 아기 상어 2

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만

www.acmicpc.net

//[C++] 백준 문제풀이 (Bruteforcing)
#include <bits/stdc++.h>


int map[50][50];
int dist[50][50];


int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    int ret = INT_MIN;
    std::cin >> n >> m;

    for (int y = 0; y < n; ++y){
        for (int x = 0; x < m; ++x){
            std::cin >> map[y][x];
        }
    }
    
    const int dr[] = {-1, 1, 0, 0, -1, -1, 1, 1};
    const int dc[] = {0, 0, -1, 1, 1, -1, 1, -1};

    for (int i = 0; i < n; ++i){
        std::fill(dist[i], dist[i] + m, -1);
    }

    
    for (int y = 0; y < n; ++y){
        for (int x = 0; x < m; ++x){
            if (map[y][x] == 0) continue;
            std::queue<std::pair<int, int>> q;
            q.push({y, x});
            dist[y][x] = 0;
            
            while(!q.empty()){
                auto [r, c] = q.front(); q.pop();
                for (int dir = 0; dir < 8; ++dir){
                    int nr = r + dr[dir];
                    int nc = c + dc[dir];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                    if (map[nr][nc] == 1) continue;
                    // 아직 방문하지 않았거나 방문했지만 이전에 안전거리가 더 큰 경우 갱신
                    if (dist[nr][nc] == -1 || dist[nr][nc] > dist[r][c] + 1){
                        q.push({nr, nc});
                        dist[nr][nc] = dist[r][c] + 1;
                    }
                }
            }
        }
    }


    for (int y = 0; y < n; ++y){
        for (int x = 0; x < m; ++x){
            ret = std::max(ret, dist[y][x]);
        }
    }

    std::cout << ret << "\n";

    return 0;
}