인프런 커뮤니티 질문&답변

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

while 한번마다 이중반복문으로 bfs 시작점을 찾았기 때문에 시간초과가 난다고 생각했습니다. 그런데 어느정도로 시간이 걸리는지 특정하지 못하겠습니다. 이중반복문이어도 x가 있을 때 바로 go를 실행하니 O(NM)이라 할 수 있나요? 시간복잡도 측면에서 어떻게 되는지 자세하게 설명 부탁드립니다 ㅜㅜ

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, M;
vector<vector<char>> graph;
vector<vector<bool>> visited;
vector<pair<int, int>> ice;
bool ok = false;
int x1, y1, x2, y2;
int cnt = 0;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

void reachable(int x, int y) {
    queue<pair<int, int>> q;
    vector<vector<bool>> check(N, vector<bool>(M, false));
    check[x][y] = true;
    q.push({x, y});

    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (check[nx][ny]) continue;

            if (graph[nx][ny] == 'L') {
                ok = true;
                return;  // 다른 백조를 찾으면 즉시 반환
            }

            if (graph[nx][ny] != 'X') {
                q.push({nx, ny});
                check[nx][ny] = true;
            }
        }
    }
}

void go(int x, int y) {
    if (graph[x][y] == 'X') {
        ice.push_back({x, y});
        return;
    }

    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
        if (visited[nx][ny]) continue;
        go(nx, ny);
    }
}

int main() {
    cin >> N >> M;
    graph.assign(N, vector<char>(M));
    visited.assign(N, vector<bool>(M, false));

    int l_count = 0;
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < M; j++) {
            graph[i][j] = s[j];
            if (graph[i][j] == 'L') {
                if (l_count == 0) {
                    x1 = i;
                    y1 = j;
                    l_count++;
                } else {
                    x2 = i;
                    y2 = j;
                }
            }
        }
    }

    int ret = 0;
    while (true) {
        reachable(x1, y1);
        if (ok) break;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j] && graph[i][j] != 'X') {
                    cnt++;
                    go(i, j);
                }
            }
        }

        // 빙판 녹이기
        for (const auto& pos : ice) {
            graph[pos.first][pos.second] = '.';
        }
        ice.clear();
        ret++;
    }

    cout << ret << endl;
    cout << cnt << endl;

    return 0;
}