[BOJ 17086] 아기 상어 2 C++

난이도: Silver 2
번호: 17086
생성일: March 3, 2023 7:26 PM
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 브루트포스 알고리즘
알고리즘, 자료 구조: Memoization
언어: C++

17086번: 아기 상어 2

C++

BFS+ Memoization

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int N, M, maxDistToShark = -1;
bool map[51][51];
bool vst[51][51];
int memo[51][51]; // 메모이제이션 배열

const int dX[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dY[] = {0, -1, -1, -1, 0, 1, 1, 1};

void reset_vst()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            vst[i][j] = false;
}

int BFS(int i, int j)
{
    // 이미 계산된 값이 있다면 바로 반환
    if (memo[i][j] != -1) return memo[i][j];

    reset_vst();
    queue<pair<int, int>> Q;
    int curDist = 1;
    Q.push({i, j});
    vst[i][j] = true;

    while (!Q.empty())
    {
        int len = Q.size();
        for (int l = 0; l < len; l++)
        {
            auto cur = Q.front();
            Q.pop();

            for (int k = 0; k < 8; k++)
            {
                int x = dX[k] + cur.first;
                int y = dY[k] + cur.second;

                if (x < 0 || y < 0 || x >= N || y >= M)
                    continue;

                if (vst[x][y])
                    continue;

                if (map[x][y] == 1)
                {
                    // 메모이제이션 배열에 저장하고 최대 거리 갱신
                    memo[i][j] = curDist;
                    maxDistToShark = max(curDist, maxDistToShark);
                    return memo[i][j];
                }

                vst[x][y] = true;
                Q.push({x, y});
            }
        }
        curDist++;
    }

    // 메모이제이션 배열에 저장하고 반환
    memo[i][j] = curDist - 1;
    return memo[i][j];
}

int main(void)
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> M;

    // 배열 입력 받기
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> map[i][j];

    // 메모이제이션 배열 초기화
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            memo[i][j] = -1;

    // 모든 빈 칸에 대해서 BFS 알고리즘 수행
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (map[i][j] == 0)
                BFS(i, j);

    // 가장 먼 거리 출력
    cout << maxDistToShark;

    return (0);
}