[삼성, 디버깅] BackTracking, Simulate, 백트래킹 시간 줄이기

 

문제

 

 

1차 코드

#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <tuple>

#define MAX_H 30
#define MAX_N 10

using namespace std;

int N, H;
bool grid[MAX_H+1][MAX_N+1];
vector<pair<int, int>> candi;
int ans = 10;

bool InRange(int x) {
    return 0 <= x && x < N;
}

bool Verify() {
    for (int j = 0; j < N; j++) {
        int id = j;
        for (int i = 0; i < H; i++) {
            if (grid[i][id]) {
                id++;
            }
            else if (id && grid[i][id - 1]) {
                id--;
            }
        }
        if (id != j) return false;
    }
    return true;
}


void FindMin(int start,int cnt) {
    if (cnt > ans) return;
    if (Verify()) 
        ans = min(ans, cnt);
    if (cnt > 3) return;

    for (int i = start; i < candi.size(); i++) {
        int y, x;
        tie(y, x) = candi[i];
        //선 겹침 
        if (InRange(x - 1) && grid[y][x - 1]) continue;
        if (InRange(x + 1) && grid[y][x + 1]) continue;
        grid[y][x] = true;
        FindMin(i +1, cnt + 1);
        grid[y][x] = false;
        
        //이거 안하면 시간 초과
        if (cnt > ans || cnt > 3) break; 
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int M;
    cin >> N >> M >> H;
    while (M--) {
        int a, b;
        cin >> a >> b;
        grid[a - 1][b - 1] = true;
    }

    for (int i = 0; i < H; i++)
        for (int j = 0; j < N; j++)
            if (!grid[i][j]) 
                candi.push_back({ i,j });

    FindMin(0, 0);

    if (ans > 3) ans = -1;
    cout << ans;

    return 0;
}

 

2차 코드

#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <tuple>

#define MAX_H 30
#define MAX_N 10

using namespace std;

int N, H;
bool grid[MAX_H+1][MAX_N+1];
vector<pair<int, int>> candi;
int ans = 10;

bool InRange(int x) {
    return 0 <= x && x < N;
}

bool Verify() {
    for (int j = 0; j < N; j++) {
        int id = j;
        for (int i = 0; i < H; i++) {
            if (grid[i][id]) id++;
            else if (id && grid[i][id - 1]) id--;
        }
        if (id != j) return false;
    }
    return true;
}

void FindMin(int start,int cnt) {
    if (cnt > ans) return;
    if (Verify()) 
        ans = min(ans, cnt);

    if (cnt > 3 || start == candi.size()) return;

    FindMin(start + 1, cnt);

    int y, x;
    tie(y, x) = candi[start];
    //선 겹침 
    if (InRange(x - 1) && grid[y][x - 1]) return;
    if (InRange(x + 1) && grid[y][x + 1]) return;
    grid[y][x] = true;
    FindMin(start + 1, cnt + 1);
    grid[y][x] = false;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int M;
    cin >> N >> M >> H;
    while (M--) {
        int a, b;
        cin >> a >> b;
        grid[a - 1][b - 1] = true;
    }

    for (int i = 0; i < H; i++)
        for (int j = 0; j < N; j++)
            if (!grid[i][j]) 
                candi.push_back({ i,j });

    FindMin(0, 0);

    if (ans > 3) ans = -1;
    cout << ans;

    return 0;
}

 

backtracking 일반적으로 하던 방식인 for문이 아닌

현재 타겟을 선택할지 말지로 나눠서 진행.

 

3차 코드

#include <iostream>


#define MAX_H 30
#define MAX_N 10

using namespace std;

int N, H;
bool grid[MAX_H + 1][MAX_N + 1];

int ans = 10;

bool InRange(int x) {
    return 0 <= x && x < N;
}

bool Verify() {
    for (int j = 0; j < N; j++) {
        int id = j;
        for (int i = 0; i < H; i++) {
            if (grid[i][id]) id++;
            else if (id && grid[i][id - 1]) id--;
        }
        if (id != j) return false;
    }
    return true;
}


bool CanSelect(int y, int x) {
    if (grid[y][x]) return false;
    //양옆 비었다.
    if (InRange(x - 1) && grid[y][x - 1]) return false;
    if (InRange(x + 1) && grid[y][x + 1]) return false;
    return true;
}


void FindMin(int r, int c, int cnt) {
    if (cnt > 3 || cnt > ans) return;
    for (int i = r; i < H; i++) {
        int j = 0;
        if (i == r) j = c; //c 보낼때 시작지점부터 보내야해!!!!!!!!!!!
        for (; j < N; j++) {
            if (!CanSelect(i, j)) continue;
            grid[i][j] = true;
            if (Verify()) ans = min(ans, cnt);
            FindMin(i, j + 1,cnt+1);
            grid[i][j] = false;

        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int M;
    cin >> N >> M >> H;
    while (M--) {
        int a, b;
        cin >> a >> b;
        grid[a - 1][b - 1] = true;
    }
    //원본상태
    if(Verify()) ans = min(ans,0);
    FindMin(0,0,1);

    if (ans > 3) ans = -1;
    cout << ans;

    return 0;
}

vector 사용하지 않고 위치로 바로 했더니 시간이 많이 줄었다.

4차와 시간 차이는  어디서 나는걸까

 

4차 코드 

// 20231002 16:29
#include <iostream>

using namespace std;

int N, H, M;
int map[30][10] = { 0 };

int ans = -1;

void input()
{
	cin >> N >> M >> H;
	for (int i = 0; i < M; i++)
	{
		int r, c;
		cin >> r >> c;
		map[r - 1][c - 1] = 1;
	}
}

bool check()
{
	for (int c = 0; c < N; c++)
	{
		int cc = c;
		for (int r = 0; r < H; r++)
		{
			if (cc - 1 >= 0 && map[r][cc - 1])
			{
				cc--;
			}
			else if (cc < N - 1 && map[r][cc] == 1)
			{
				cc++;
			}
		}
		if (cc != c)
		{
			return false;
		}
	}
	return true;
}

void select(int sr, int sc, int cnt, int target_cnt)
{
	if (cnt == target_cnt)
	{
		if (check())
		{
			ans = target_cnt;
			return;
		}
		else
		{
			return;
		}
	}
	for (int r = sr; r < H; r++)
	{
		for (int c = sc; c < N - 1; c++)
		{
			if (map[r][c] == 0)
			{
				map[r][c] = 1;
				if (c == N - 2)
				{
					select(r + 1, 0, cnt + 1, target_cnt);
				}
				else
				{
					select(r, c + 1, cnt + 1, target_cnt);
				}
				map[r][c] = 0;
			}
		}
	}
}

int main()
{
	input();
	for (int i = 0; i <= 3; i++)
	{
		select(0, 0, 0, i);
		if (ans != -1)
		{
			break;
		}
	}
	cout << ans;
}

 

다른 분 코드 

backtracking을 단순 for문으로 진행. 훨씬 빠르다.