글 읽기 - 시간 초과 왜뜨는지 잘모르겠습니다...ㅜ

kjds1235 5년 전 0

아래와 같이 코드를 작성했는데...ㅠㅠ

다른 분들과 다를게없어 보이는데 왜 시간초과가 뜨는걸까요 ㅠ 고수님들 부탁드립니다.

#include <cstdio>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

struct index
{
    int x;
    int y;
};

int n, m;
int chicken_cnt;
int house_cnt;
struct index houselist[50];
int house_dist[50];
struct index chickenlist[50];
int index_array[50];
int arr[50];
int min_val = 0x7fffffff;

void InputData()
{

    scanf("%d %d", &n, &m);
    int temp;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &temp);
            if (temp == 1)
            {
                houselist[house_cnt].x = i;
                houselist[house_cnt].y = j;
                house_cnt++;
            }
            else if (temp == 2)
            {
                chickenlist[chicken_cnt].x = i;
                chickenlist[chicken_cnt].y = j;
                chicken_cnt++;
            }
        }
    }

}

void calc_dist()
{
    int dist = 0;
    for (int i = 0; i < house_cnt; i++)
    {
        int tempdist = 0x7fffffff;
        for (int j = 0; j < m; j++)
        {
            int temp2 = abs(chickenlist[arr[j]].x - houselist[i].x) + abs(chickenlist[arr[j]].y - houselist[i].y);
            if (temp2 < tempdist)
            {
                tempdist = temp2;
            }
        }
        dist = dist + tempdist;
    }
    if (dist < min_val)
    {
        min_val = dist;
    }
}

void DFS(int cnt, int indexing)
{
    if (cnt == m)
    {
        //  print_dist();
        calc_dist();
    }
    else
    {
        for (int i = indexing; i < chicken_cnt; i++)
        {
            arr[cnt] = i;
            DFS(cnt + 1, i + 1);
            arr[cnt] = 0;
        }
    }
}

int main(void)
{
    InputData();

    DFS(0, 0);
    printf("%d", min_val);
    return 0;
}

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

문제

문제

출처

ICPC

시간 초과 왜뜨는지 잘모르겠습니다...ㅜ

kjds1235 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말