[알고리즘] c++ cpp 상어 시리즈(아기상어2)

포인트

1. BFS 를 잘 이해하는가?

2. 8가지 방향으로 bfs 를 도는 방법 입니다. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <tuple>

using namespace std;

int n, m, answer;
int map[51][51];
bool visited[51][51];
vector<pair<int, int>> vc;

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; // 8방향
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};


int bfs(int a, int b) {
    queue<tuple<int, int, int>> q;
    q.emplace(a, b, 0);
    visited[a][b] = true;

    while (!q.empty()) {
        int x, y, cnt;
        tie(x, y, cnt) = q.front();
        q.pop();

        if (map[x][y] == 1) { // 종료 조건
            return cnt;
        }

        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

            if (!visited[nx][ny]) {
                q.emplace(nx, ny, cnt + 1);
                visited[nx][ny] = true;
            }
        }
    }
}


int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == 0) {
                vc.emplace_back(i, j);
            }
        }
    }

    for (int i = 0; i < vc.size(); i++) {
        memset(visited, false, sizeof(visited));
        int x = vc[i].first;
        int y = vc[i].second;

        int value = bfs(x, y);
        answer = max(answer, value);
    }

    cout << answer << '\n';
    return 0;
}