인프런 커뮤니티 질문&답변

안녕하세요 큰돌 강사님!

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

지워야 할 치킨집의 수 만큼 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;
}