글 읽기 - 시간초과 관련해서 도움 요청합니다.

minjoonist 3년 전 0

안녕하세요. 치킨 배달 문제를 풀었지만 시간 초과가 나왔습니다. 시간 초과에서 전체 알고리즘을 다시 짜야 하는지, 아님 일부분을 개선하여 해결 할 수 있는지, 그리고 어떻게 바꿔야 하는지 잘 모르겠습니다.

제 코드는 일단 백트랙킹으로 가능한 치킨집의 경우를 모두 잡아내고 그뒤 각각의 집에서 BFS를 돌려 가장 가까이 있는 치킨집의 거리를 구하는 방식입니다. 도와주시면 정말 감사하겠습니다.

#include <iostream>
#include <cmath>
#include <queue>
#include <climits>
#define MAX 51
using namespace std;
using pii=pair<int, int>;

const int dx[]={0, 0, 1, -1, -1, -1, 1, 1};
const int dy[]={1, -1, 0, 0, -1, 1, -1, 1};
int n, m, mp[MAX][MAX], cnt, res=INT_MAX;

int dist(int x1, int y1, pii xy){return abs(x1-xy.first)+abs(y1-xy.second);}

pii bfs(int x, int y)
{
    queue<pii> q;
    bool visited[MAX][MAX]={};

    q.push({x, y});
    visited[x][y]=true;

    while(!q.empty()){
        int cx=q.front().first, cy=q.front().second;q.pop();
        for(int i=0; i<8; i++){
            int nx=cx+dx[i], ny=cy+dy[i];
            if(nx<0 || ny<0 || nx>=n || ny>=n) continue;

            if(!visited[nx][ny]){
                if(mp[nx][ny]==2) return make_pair(nx, ny);
                q.push({nx, ny});
                visited[nx][ny]=true;
            }
        }
    }
}
int calc()
{
    int cnt=0;
    for(int i=0; i<n; i++) for(int j=0; j<n; j++){
        if(mp[i][j]==1){
            cnt+=dist(i, j, bfs(i, j));
        }
    }
    return cnt;
}
void bt(int x)
{
    if(!m){
        res=min(res, calc());
        return;
    }
    for(int i=x; i<n; i++){
        for(int j=0; j<n; j++){
            if(mp[i][j]==2){
                mp[i][j]=0;
                m--;
                bt(i);
                mp[i][j]=2;
                m++;
            }
        }
    }
}
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin>>n>>m;
    for(int i=0; i<n; i++) for(int j=0; j<n; j++){
        cin>>mp[i][j];
        if(mp[i][j]==2) cnt++;
    }
    m=cnt-m;
    bt(0);
    cout<<res;
    return 0;
}

shg9411 3년 전 0

bfs를 굳이 하기보다는 그냥 선택된 치킨집들과 거리 계산을 하는 것이 낫지 않을까요? M이 최대 13이니깡

minjoonist 3년 전 0

의견 감사합니다. 이렇게 하려면 코드를 아예 다시 짜야 할것 같네요..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 관련해서 도움 요청합니다.

minjoonist 3년 전 0

shg9411 3년 전 0

minjoonist 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말