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

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

17086번: 아기 상어 2

 

bfs로 금방 해결할 수 있는 문제다. 아이디어는 매우 간단하다. 아래를 구현할 수 있으면 된다. 

모든 칸마다 안전 거리를 구하고, 최대값을 계속 갱신한다!

 

나는 문제를 풀기 위해 세 개의 배열을 사용했다. 

int init[50][50] → 초기 입력값 (변하지 않음)
int use[50][50] → bfs 탐색할 때 사용하는 배열 (계속 바뀜)
int visit[50][50] → 방문 배열 (계속 바뀜)

 

매 칸마다 bfs를 사용하기 때문에 use 배열과 visit 배열은 매번 초기값으로 바꿔줘야 한다. 이를 초기값으로 바꿔주는 함수가 정답 코드에서 initialize() 함수다.

 

bfs 함수 이름은 get_safe이며 해당 칸의 안전거리를 반환해준다. 따라서 메인 함수에서 반환값과 최대값을 비교해가면서 최대값을 계속 갱신시켜주면 된다. 

 

이 문제는 특이하게 대각선 이동이 가능하다. 값의 이동은 정답 코드의 move 배열을 참고하길 바란다. 

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int init[50][50];
int use[50][50];
int visit[50][50];
int row, col;

int get_safe(int x, int y, int move[8][2]){
    // bfs로 1이 나올때까지 탐색
    queue<pair<int, int>> q;
    q.push({x, y});
    visit[x][y] = 1;
    int ret = 0;
    
    int m_x, m_y;
    while(!q.empty()){
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        if(init[x][y] == 1){
            ret = use[x][y];
            break;
        }
        
        for(int i = 0; i < 8; i++){
            m_x = x + move[i][0];
            m_y = y + move[i][1];
            if(m_x >= 0 && m_y >= 0 && m_x < 50 && m_y < 50){
                if(!visit[m_x][m_y]){
                    visit[m_x][m_y] = 1;
                    use[m_x][m_y] = use[x][y] + 1;
                    q.push({m_x, m_y});
                }
            }
        }
        
    }
    return ret;
}

void initialize(){
    // use를 init로 초기화, visit은 모두 0으로 초기화
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            use[i][j] = init[i][j];
            visit[i][j] = 0;
        }
    }
    
}

int main(){
    int move[8][2] = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
    int tmp;
    int Max = 0;
    cin >> row >> col;
    
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            cin >> tmp;
            init[i][j] = tmp;
            use[i][j] = tmp;
        }
    }
    
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            if(init[i][j] == 0){
                initialize();
                Max = max(Max, get_safe(i, j, move));
            }
        }
    }
    
    cout << Max << endl;
    
    return 0;
}