• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

3-A 치킨문제 시간초과가 납니다

22.07.10 23:06 작성 조회수 156

1

안녕하세요 큰돌 강사님!

저는 백트래킹 방식으로 풀어보려고 코드를 작성했습니다.

 

지워야 할 치킨집의 수 만큼 board에서 2-> 0으로 바꾼 뒤 남아있는 치킨집 들과 거리를 계산해서 최소값을 구하는 방식으로 코드를 작성했습니다.

강의에서 나온 조합 리스트들을 먼저 구하고 그 리스트 만큼 거리 계산을 해주는 방식과 제가 작성한 조합이 완성 될 때마다 계산해 주는 방식의 어떤 차이로 인해 시간초과가 나는지 궁금합니다..!

(combi 함수 작성..! 문제 풀 때 생각날 만큼 다시 교안을 봐야겠습니다.)

아래는 저의 코드입니다.

#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#define X second
#define Y first
using namespace std;
int n,m,sz;
int board[54][54];
bool vst[54][54];
vector<pair<int,int>> c;
vector<pair<int,int>> h;
int ans = 987654321;

void func(int k){
	if(k == sz){
		//거리 계산 로직
		int ret = 0;
		for(auto hh: h){
			int tmp = 987654321;
			for(auto cc: c){
				if(board[cc.Y][cc.X] == 2){
					tmp = min(tmp,(abs(cc.X - hh.X) + abs(cc.Y - hh.Y)));
				}
			}
			ret += tmp;
		}
		ans = min(ans, ret);
		return;
	}
	for(int i=0; i<c.size(); i++){
		if(!vst[c[i].Y][c[i].X]){
			vst[c[i].Y][c[i].X] = 1;
			board[c[i].Y][c[i].X] = 0;
			func(k+1);
			vst[c[i].Y][c[i].X] = 0;
			board[c[i].Y][c[i].X] = 2; 
		}
	}
} 
int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin >> board[i][j];
			if(board[i][j] == 1){
				h.push_back({i,j});
			}
			if(board[i][j] == 2){
				c.push_back({i,j});				
			}
		}
	}
	sz = c.size() - m; //없애야 하는 치킨집의 수
	func(0);
	cout << ans;
	return 0;
}

답변 2

·

답변을 작성해보세요.

0

dongdong님의 프로필

dongdong

질문자

2022.07.10

아... ! 큰돌 강사님 제가 짠 코드가 혹시

폐업하지 않는 치킨집( m개)의 조합을  찾는게 아닌 폐업한 치킨집(c.size() - m)들의 조합을 계산해서 시간초과가 발생한 건가요 ?!

 

제가 작성한 코드의 최악의경우)

50x50 전부 치킨집일 때

2500 - 13 = 2487개의 폐업한 치킨집들을 확인

때문이 맞을까요?

0

안녕하세요. ㅎㅎ

1. 왜 백트래킹으로 풀어야 한다고 생각하시나요?

2. 이 코드 제출하면 맞는다고 뜨나요?

 

감사합니다. 

강사 큰돌 올림.

dongdong님의 프로필

dongdong

질문자

2022.07.11

1. 폐업을 먼저 시켜놓고 폐업하지 않은 치킨집들로 구한 치킨거리의 모든 경우의 수를 확인해서 최소값을 구해야한다고 생각해서였습니다.

 

2. 예제 input은 다 맞게 나오지만 코드를 제출하면 시간초과가 발생합니다..

 

안녕하세요. HAN님. ㅎㅎ 

 

1. 이 코드는 백트래킹이 아닙니다. 

백트래킹이 뭐라고 생각하시나요? 백트래킹은 완전탐색에서 가지치기를 한 겁니다. 어떠한 경로는 어떠한 경우의 수는 탐색하지 않는 것이죠. 이 코드는 완전탐색에 가깝습니다. 

 

나중에 풀게 될 백준 - 색종이 붙이기 문제의 제 코드를 보면 다음과 같습니다. 

void dfs(int y, int x, int cnt){ 

if(cnt >= ret) return;   

이런식으로 되어있습니다. (나중에 풀게 되실겁니다.)

자, 여기서 if(cnt >= ret) return 을 보시면 "이미 최적값을" 찾았을 경우에는 해당 함수를 return 한다라고 되어있죠? 

그러나 HAN님의 코드에는 어디에도 그러한 걸 찾아볼 수가 없습니다. 

 

2. 이 문제는 백트래킹으로 풀면 안됩니다. 

이 문제는 

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램

이런 문제죠? 

근데 여기서 "먼저 M개를" 골랐을 때 이 값이 최적해라는 증명은 어떻게 하시나요? 

내가 지금 고른 M개가 치킨거리가 가장 작게 될 것이라는 증명은 어떻게 하실 수 있나요? 

불가능합니다. 그렇기 때문에 이 문제는 "모든 경우의 수"를 다 탐색해야 하는 것입니다. 

 

3. 시간초과가 나는 이유는 "완전탐색"으로 했기 때문입니다. 

완전탐색과 "조합"의 차이는 순서입니다. 예를 들어 1, 2, 3을 탐색한다라고 했을 때 

조합은 1, 2, 3 이렇게 딱 한번의 경우의 수 밖에 없습니다. 

하지만 완전탐색은, 순열을 생각하면 됩니다. 

1, 2, 3

1, 3, 2

2, 1, 3

2, 3, 1

...

이런식으로 순서에 따라 경우의수가 더 생기는 것이죠. 

 

물론 완전탐색을 조합이라고 하는 것도 있지만... 무튼. 

굳이 이문제에서 M개를 고르는 순서가 필요할까요? 1, 2, 3 이렇게 고르던, 3, 2, 1이렇게 고르던 고르기만 하면 되는 것이죠.

그러나 HAN님의 코드는 "순서"를 신경쓴 완탐이기 때문에 시간초과가 나는 것입니다. 

예를 들어 10P3과 10C3의 차이를 생각해보시면 간단합니다. 

 

감사합니다. 

강사 큰돌 올림.

 

dongdong님의 프로필

dongdong

질문자

2022.07.11

크.. 큰돌 강사님 하나하나 다 설명해주셔서 감사합니다.  강사님 덕분에 이해가 됐습니다.

아좌좌~