https://www.acmicpc.net/problem/17086
시간 제한 | 메모리 제한 | 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();
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 17266번 C++ 풀이 (0) | 2022.04.02 |
---|---|
백준 2512번 C++ 풀이 (0) | 2022.04.01 |
백준 16956번 C++ 풀이 (0) | 2022.03.22 |
백준 2012번 C++ 풀이 (0) | 2022.03.22 |
백준 2947번 C++ 풀이 (0) | 2022.03.22 |