[백준 17086번] 아기 상어 2

문제 링크

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

 

문제 요약

임의의 점 \((i, j)\)의 안전거리는 \((i, j)\)에서 시작해서 아기 상어가 있는 곳까지의 최소 거리를 의미한다. 여기서 거리는 인접한 8방향(상하좌우 및 대각선)으로 이동한 칸 수로 계산한다.

 

격자판 위의 모든 점들 중에서 안전거리가 최대인 값을 찾아 출력하는 것이 이 문제의 목표이다.

 

문제 풀이

기본적인 풀이

너비 우선 탐색(이하 BFS)을 이용하면 임의의 점 \((i, j)\)에서 가장 가까운 아기 상어까지의 거리를 계산할 수 있다. 그리고 N과 M의 크기가 작으므로 모든 점들에 대해서 BFS를 한 번씩 돌려도 제한시간 내에 충분히 답을 구할 수 있다. 아래 더보기 버튼을 누르면 이 방법으로 푼 코드를 볼 수 있다.

 

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>

using namespace std;

const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int n, m, A[51][51], D[51][51];

bool isPossible(int x, int y) {
    if (x == -1 || x == n || y == -1 || y == m) {
        return false;
    }
    
    return true;
}

int bfs(pair<int, int> src) {
    queue<pair<int, int>> q;
    memset(D, -1, sizeof(D));
    
    q.push(src);
    D[src.first][src.second] = 0;
    
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        if (A[x][y] == 1) {
            return D[x][y];
        }
        
        for (int i = 0 ; i < 8 ; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            
            if (isPossible(nx, ny) && D[nx][ny] == -1) {
                q.push({ nx, ny });
                D[nx][ny] = D[x][y] + 1;
            }
        }
    }
    
    return 0;
}

int main() {
    scanf("%d%d", &n, &m);
    
    for (int i = 0 ; i < n ; ++i) {
        for (int j = 0 ; j < m ; ++j) {
            scanf("%d", &A[i][j]);
        }
    }
    
    int ans = 0;
    
    for (int i = 0 ; i < n ; ++i) {
        for (int j = 0 ; j < m ; ++j) {
            if (A[i][j] == 0) {
                ans = max(ans, bfs({ i, j }));
            }
        }
    }
    
    printf("%d\n", ans);
}

 

조금 더 빠르게 풀어보기

격자판 위의 모든 점에 대해서 각각 BFS를 돌리는 것이 비효율적이라고 생각할 수 있다. 만약 문제에서 주어지는 N과 M의 최대 크기가 지금보다 더 컸다면 위 방법으로는 이 문제를 풀 수 없었을 것이다. 조금 더 빠르게 풀 수 있는 방법은 없을까?

 

BFS를 돌리기 위해서 암시적으로 모델링 한 그래프가 무향 그래프라는 점을 생각해 보자. 그러면 각 점에서 아기 상어까지의 최단 거리와 아기 상어에서 각 점까지의 최단 거리가 같다는 것을 알 수 있다. 따라서 아기 상어가 있는 모든 지점들을 시작점으로 잡고 BFS를 돌리면 BFS 한 번에 모든 지점들의 안전거리를 구할 수 있다. 아래 더보기 버튼을 누르면 더 빠르게 문제를 해결하는 코드를 볼 수 있다.

 

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>

using namespace std;

const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int n, m, A[51][51], D[51][51];

bool isPossible(int x, int y) {
    if (x == -1 || x == n || y == -1 || y == m) {
        return false;
    }
    
    return true;
}

int main() {
    scanf("%d%d", &n, &m);
    
    for (int i = 0 ; i < n ; ++i) {
        for (int j = 0 ; j < m ; ++j) {
            scanf("%d", &A[i][j]);
        }
    }
    
    memset(D, -1, sizeof(D));
    queue<pair<int, int>> q;
    
    for (int i = 0 ; i < n ; ++i) {
        for (int j = 0 ; j < m ; ++j) {
            if (A[i][j] == 1) {
                D[i][j] = 0;
                q.push({ i, j });
            }
        }
    }
    
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for (int i = 0 ; i < 8 ; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            
            if (isPossible(nx, ny) && D[nx][ny] == -1) {
                D[nx][ny] = D[x][y] + 1;
                q.push({ nx, ny });
            }
        }
    }
    
    int ans = 0;
    
    for (int i = 0 ; i < n ; ++i) {
        for (int j = 0 ; j < m ; ++j) {
            ans = max(ans, D[i][j]);
        }
    }
    
    printf("%d\n", ans);
}