글 읽기 - 시간초과 문제

shin10934 5년 전 0

조합을 이용하여 모든 경우를 만들고, bfs로 집마다 치킨 거리를 구해서 다 더하는 방식으로 구현했습니다. 그런데 시간초과가 뜨는데 이유를 잘 모르겠네요..

//
//  main.cpp
//  baek치킨배달
//
//  Created by ShinSeungYeol on 2018. 8. 29..
//  Copyright © 2018년 ShinSeungYeol. All rights reserved.
//

#include <cstdio>
#include <climits>
#include <queue>

using namespace std;
enum{EMPTY=0, HOUSE=1, CHICKEN=2}; 

typedef struct{
    int row,col;
}Building;

typedef struct{
    int row,col,depth;
}Node;

int n,m; // n: map size, m: 살아 남은 치킨 집 개수,
int map[50][50]; //map 최대사이즈 : 50
Building houses[100]; //house 최대는 2n
Building chickens[13]; 
int num_of_houses=0;  // 집의 총 개수
int num_of_chickenes=0; // 치킨 집의 총 개수
int min_of_distance = INT_MAX;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

bool is_range(int r, int c);
int calc_nearest_distance(int idx_of_house);
void combinate(int idx_of_chicken, int cnt);

int main(int argc, const char * argv[]) {
    scanf("%d %d",&n,&m);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int type;
            scanf("%d",&type);
            if(type==HOUSE){
                houses[num_of_houses].row = i;
                houses[num_of_houses++].col = j;
            }
            else if(type==CHICKEN){
                chickens[num_of_chickenes].row = i;
                chickens[num_of_chickenes++].col = j;
            }
            map[i][j] = type;
        }
    }
    combinate(0,0);

    printf("%d\n",min_of_distance);
    return 0;
}
bool is_range(int r, int c){
    return (r>=0&&r<n&&c>=0&&c<n);
}
int calc_nearest_distance(int idx_of_house){
    queue<Node> q;
    Node first;
    first.row = houses[idx_of_house].row;
    first.col = houses[idx_of_house].col;
    first.depth = 0;
    int check[50][50] = {false};
    check[first.row][first.col] =true;
    q.push(first);
    while(!q.empty()){
        int cur_r = q.front().row;
        int cur_c = q.front().col;
        int depth = q.front().depth;
        q.pop();
        
        for(int i=0; i<4; i++){
            int next_r = cur_r + dir[i][0];
            int next_c = cur_c + dir[i][1];
            if(!is_range(next_r, next_c)||check[next_r][next_c]) continue;
            if(map[next_r][next_c]!=CHICKEN){
                Node tmp;
                tmp.row = next_r;
                tmp.col = next_c;
                tmp.depth = depth+1;
                check[tmp.row][tmp.col] = true;
                q.push(tmp);
            }
            else if(map[next_r][next_c]==CHICKEN) return depth+1;
            
        }
    }
    return -1; //치킨집 없을 경우, 문제 특성상 불가능
}

void combinate(int idx_of_chicken, int cnt){
    if(cnt>=num_of_chickenes-m){ // m개의 치킨 집을 선택하는 것이 아닌 총 치킨집의 개수-m개의 치킨 집을
                                // 빈 곳으로 만들어 주는 방식
        int sum_of_distance = 0;
        for(int i=0; i<num_of_houses; i++)
            sum_of_distance+=calc_nearest_distance(i);
        if(sum_of_distance<min_of_distance)
            min_of_distance = sum_of_distance;
        return;
    }
    for(int i=idx_of_chicken; i<num_of_chickenes; i++){
        map[chickens[i].row][chickens[i].col] = EMPTY;
        combinate(i+1,cnt+1);
        map[chickens[i].row][chickens[i].col] = CHICKEN;
    }
    
}

coronal95 5년 전 1

저도 확실한 건 아니지만 ...

* m개의 치킨 집을 선택하는 것이 아닌 총 치킨집의 개수-m개의 치킨 집을 빈 곳으로 만들어 주는 방식 *

이 아닌 그냥 M개의 치킨 집을 선택 해도 되지 않을까요?

치킨 거리를 구할 때에도 그냥 |집의 x좌표 - 치킨집의 x좌표|+|집의 y좌표-치킨집의 y좌표| 해주면 될 것 같은데요 ㅎㅎ

shin10934 5년 전 0

댓글 감사합니다. stl queue push, pop이 생각보다 느려서 발생한 문제였네요. 정말 감사합니다. 해결한 소스 코드도 올리겠습니다

//
//  main.cpp
//  baek치킨배달
//
//  Created by ShinSeungYeol on 2018. 8. 29..
//  Copyright © 2018년 ShinSeungYeol. All rights reserved.
//

#include <cstdio>
#include <climits>
#include <cmath>
#include <queue>

using namespace std;
enum{EMPTY=0, HOUSE=1, CHICKEN=2};

typedef struct{
    int row,col;
}Building;

typedef struct{
    int row,col,depth;
}Node;

int n,m; // n: map size, m: 살아 남은 치킨 집 개수,
int map[50][50]; //map 최대사이즈 : 50
Building houses[100]; //house 최대는 2n
Building chickens[13];
int num_of_houses=0;
int num_of_chickenes=0;
int min_of_distance = INT_MAX;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

bool is_range(int r, int c);
int calc_nearest_distance(int idx_of_house);
void combinate(int idx_of_chicken, int cnt);

int main(int argc, const char * argv[]) {
    scanf("%d %d",&n,&m);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int type;
            scanf("%d",&type);
            if(type==HOUSE){
                houses[num_of_houses].row = i;
                houses[num_of_houses++].col = j;
            }
            else if(type==CHICKEN){
                chickens[num_of_chickenes].row = i;
                chickens[num_of_chickenes++].col = j;
            }
            map[i][j] = type;
        }
    }
    combinate(0,0);

    printf("%d\n",min_of_distance);
    return 0;
}
bool is_range(int r, int c){
    return (r>=0&&r<n&&c>=0&&c<n);
}
/*int calc_nearest_distance(int idx_of_house){
    queue<Node> q;
    Node first;
    first.row = houses[idx_of_house].row;
    first.col = houses[idx_of_house].col;
    first.depth = 0;
    int check[50][50] = {false};
    check[first.row][first.col] =true;
    q.push(first);
    while(!q.empty()){
        int cur_r = q.front().row;
        int cur_c = q.front().col;
        int depth = q.front().depth;
        q.pop();
        
        for(int i=0; i<4; i++){
            int next_r = cur_r + dir[i][0];
            int next_c = cur_c + dir[i][1];
            if(!is_range(next_r, next_c)||check[next_r][next_c]) continue;
            if(map[next_r][next_c]!=CHICKEN){
                Node tmp;
                tmp.row = next_r;
                tmp.col = next_c;
                tmp.depth = depth+1;
                check[tmp.row][tmp.col] = true;
                q.push(tmp);
            }
            else if(map[next_r][next_c]==CHICKEN) return depth+1;
            
        }
    }
    return -1; //치킨집 없을 경우, 문제 특성상 불가능
}시간 초과가 뜬 이유: stl queue*/
int calc_nearest_distance(int idx_of_house){
    int min = INT_MAX,house_r = houses[idx_of_house].row,house_c = houses[idx_of_house].col;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if((i==house_r&&j==house_c)||(map[i][j]!=CHICKEN)) continue;
            int d = abs(double(i-house_r))+abs(double(j-house_c));
            if(d<min) min = d;
        }
    }
    return min;
}

void combinate(int idx_of_chicken, int cnt){
    if(cnt>=num_of_chickenes-m){
        int sum_of_distance = 0;
        for(int i=0; i<num_of_houses; i++)
            sum_of_distance+=calc_nearest_distance(i);
        if(sum_of_distance<min_of_distance)
            min_of_distance = sum_of_distance;
        return;
    }
    for(int i=idx_of_chicken; i<num_of_chickenes; i++){
        map[chickens[i].row][chickens[i].col] = EMPTY;
        combinate(i+1,cnt+1);
        map[chickens[i].row][chickens[i].col] = CHICKEN;
    }
    
}

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

문제

문제

출처

ICPC

시간초과 문제

shin10934 5년 전 0

coronal95 5년 전 1

shin10934 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말