백준 17086번 C++ 풀이

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

17086번: 아기 상어 2

시간 제한	메모리 제한	solved.ac 티어
2초	512MB	실버 2

문제

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자. 

입력

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

출력

첫째 줄에 안전 거리의 최댓값을 출력한다.

---

상어가 없는 칸에서 bfs를 돌리면서 각 위치에서의 안전거리의 최솟값을 구해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
#define MAX 50

int board[MAX][MAX];
int xlen, ylen; // 입력의 크기
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

void input() {
    cin >> ylen >> xlen;
    
    for(int y = 0; y < ylen; y++) {
        for(int x = 0; x < xlen; x++) {
            cin >> board[y][x];
        }
    }
}

int bfs(int x, int y) { // x, y: 현재 위치
    bool visit[MAX][MAX] = {false, };
    queue<tuple<int, int, int>> q; // (x, y, dist)
    q.push(make_tuple(x, y, 0));
    visit[y][x] = true;

    while(!q.empty()) {
        int orix = get<0>(q.front()); // 원래 좌표
        int oriy = get<1>(q.front());
        int dist = get<2>(q.front());
        q.pop();

        if (board[oriy][orix] == 1) {
            return dist;
        }

        for(int i = 0; i < 8; i++) {
            int nx = orix + dx[i]; // 8방향으로 움직였을 때의 좌표
            int ny = oriy + dy[i];
            if (nx < 0 || nx >= xlen) continue; // 입력받은 그래프를 벗어나면 반복문으로 다시 돌아간다.
            if (ny < 0 || ny >= ylen) continue;
            if (visit[ny][nx]) continue;

            visit[ny][nx] = true;
            q.push(make_tuple(nx, ny, dist + 1));
        }
    }
}

void solution() {
    int max_dist = -1;

    for (int y = 0; y < ylen; y++){
        for(int x = 0; x < xlen; x++) {
            if (board[y][x] != 1) { // 상어가 없는 자리라면
                max_dist = max(max_dist, bfs(x, y));  // 안전거리 비교
            }
        }
    }
    cout << max_dist;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    input();
    solution();
}