글 읽기 - c++ bfs 풀이 시간 초과 문제입니다 ㅜㅜ

ast99 1년 전 0

A -> B,
B -> A
해당 순서로 bfs를 2번 도는 함수를 2번 호출하여, 비교하였는데 계속 시간초과가납니다 ㅠㅠ
어떤 부분을 놓치고 있는 걸까요 ..
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <numeric>
#include <string>
#include <queue>
#include <map>
#include <climits>
#include <string.h>


using namespace std;

const int A1 = 0;
const int A2 = 1;
const int B1 = 2;
const int B2 = 3;

vector<int> dx = {0, 0, 1, -1};
vector<int> dy = {1, -1, 0, 0};


vector<pair<int, int>> coor;
int aFlag = 0, bFlag = 0;

int bfs(int n, int m, char type, vector<vector<int>> &mapp, vector<vector<int>> &visited) {
    vector<vector<pair<int, int>>> path(n + 1, vector<pair<int, int>>(m + 1, pair<int, int>(2, 0)));
    queue<pair<int, int>> q;
    int result = 0;

    if (type == 'A') {
        q.push(coor[A1]);
        visited[coor[A1].first][coor[A1].second] = 1;
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if (x == coor[A2].first && y == coor[A2].second) {
                mapp[x][y] = 1;
                while (true) {
                    x = path[x][y].first;
                    y = path[x][y].second;

                    mapp[x][y] = 1;
                    if (x == coor[A1].first && y == coor[A1].second) {
                        break;
                    }
                }
                break;
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (0 <= nx && nx < n + 1 && 0 <= ny && ny < m + 1 && visited[nx][ny] != 1) {
                    visited[nx][ny] = 1;
                    path[nx][ny].first = x;
                    path[nx][ny].second = y;
                    q.emplace(nx, ny);
                }
            }
        }

        for (int i = 0; i < n + 1; i++) {
            fill(visited[i].begin(), visited[i].end(), 0);
        }


        while (!q.empty()) q.pop();
        q.push(coor[B1]);
        visited[coor[B1].first][coor[B1].second] = 1;

        while (!q.empty()) {

            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            if (x == coor[B2].first && y == coor[B2].second) {
                aFlag = 1;
                mapp[x][y] = 1;
                while (true) {
                    x = path[x][y].first;
                    y = path[x][y].second;

                    mapp[x][y] = 1;
                    if (x == coor[B1].first && y == coor[B1].second) {
                        break;
                    };
                }
                break;
            }

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (0 <= nx && nx < n + 1 && 0 <= ny && ny < m + 1 && visited[nx][ny] != 1 && mapp[nx][ny] != 1) {
                    visited[nx][ny] = 1;
                    path[nx][ny].first = x;
                    path[nx][ny].second = y;
                    q.emplace(nx, ny);
                }
            }
        }
        if (aFlag == 0)     return -1;
    } else {
        q.push(coor[B1]);
        visited[coor[B1].first][coor[B1].second] = 1;
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if (x == coor[B2].first && y == coor[B2].second) {
                mapp[x][y] = 1;
                while (true) {
                    x = path[x][y].first;
                    y = path[x][y].second;

                    mapp[x][y] = 1;
                    if (x == coor[B1].first && y == coor[B1].second) {
                        break;
                    }
                }
                break;
            }

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (0 <= nx && nx < n + 1 && 0 <= ny && ny < m + 1 && visited[nx][ny] != 1) {
                    visited[nx][ny] = 1;
                    path[nx][ny].first = x;
                    path[nx][ny].second = y;
                    q.emplace(nx, ny);
                }
            }
        }

        for (int i = 0; i < n + 1; i++) {
            fill(visited[i].begin(), visited[i].end(), 0);
        }


        while (!q.empty()) q.pop();
        q.push(coor[A1]);
        visited[coor[A1].first][coor[A1].second] = 1;

        while (!q.empty()) {

            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            if (x == coor[A2].first && y == coor[A2].second) {
                bFlag = 1;
                mapp[x][y] = 1;
                while (true) {
                    x = path[x][y].first;
                    y = path[x][y].second;

                    mapp[x][y] = 1;
                    if (x == coor[A1].first && y == coor[A1].second) {
                        break;
                    };
                }
                break;
            }

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (0 <= nx && nx < n + 1 && 0 <= ny && ny < m + 1 && visited[nx][ny] != 1 && mapp[nx][ny] != 1) {
                    visited[nx][ny] = 1;
                    path[nx][ny].first = x;
                    path[nx][ny].second = y;
                    q.emplace(nx, ny);
                }
            }
        }
        if (bFlag == 0)     return -1;
    }

    for (int i = 0; i < n + 1; i++) {
        for (int j = 0; j < m + 1; j++) {
            if (mapp[i][j] == 1) {
                result += 1;
            }
        }
    }

    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < 4; i++) {
        int tmp1, tmp2;
        cin >> tmp1 >> tmp2;
        coor.emplace_back(tmp1, tmp2);
    }

    vector<vector<int>> mapp(n + 1, vector<int>(m + 1, 0));
    vector<vector<int>> visited(n + 1, vector<int>(m + 1, 0));

    int result = bfs(n, m, 'A', mapp, visited);

    for (int i = 0; i < n + 1; i++) fill(visited[i].begin(), visited[i].end(), 0);
    for (int i = 0; i < n + 1; i++) fill(mapp[i].begin(), mapp[i].end(), 0);

    result = min(result, bfs(n, m, 'B', mapp, visited));

    if (result == -1)   cout << "IMPOSSIBLE";
    else                cout << result + 1;


    return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

c++ bfs 풀이 시간 초과 문제입니다 ㅜㅜ

ast99 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
