글 읽기 - 왜 백트래킹할때 메인함수에서 시작하는지??

kng0258 3년 전 1

밑에는 제가 남들 하는데로 보고 짜서 맞은 코드인데용

왜 메인함수에 이중 for문과 백트래킹 함수 SetWall() 안의 이중 for문이 같아서

메인에서 SetWall(0)을 줘도 결과는 같은데

메인에서 이중 for문을 돌면서 최초의 0을 찾는걸까요??

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>

using namespace std;

int N, M;
int Lab[8][8];
int MaxVal = 0;
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };

void Spread() {
	int tmpLab[8][8];
	queue<pair<int,int>> q;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			tmpLab[i][j] = Lab[i][j];
			if (tmpLab[i][j] == 2) {
				q.push(make_pair(i, j));
			}
		}
	}

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; ++i) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;

			if (tmpLab[ny][nx] == 0) {
				tmpLab[ny][nx] = 2;
				q.push(make_pair(ny, nx));
			}
		}
	}
	int cnt = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (tmpLab[i][j] == 0)
				cnt++;
		}
	}
	if (cnt > MaxVal) MaxVal = cnt;
}

void SetWall(int cnt) {
	if (cnt == 3) {
		Spread();
		return;
	}

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (Lab[i][j] == 0) {
				Lab[i][j] = 1;
				SetWall(cnt + 1);
				Lab[i][j] = 0;
			}
		}
	}
}

int main() {

	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			scanf("%d", &Lab[i][j]);
		}
	}

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (Lab[i][j] == 0) {
				Lab[i][j] = 1;
				SetWall(1);
				Lab[i][j] = 0;
			}
		}
	}

	printf("%d", MaxVal);

	return 0;
}

sait2000 3년 전 1

거기까지 생각을 못 해서 그런 거 아닐까요

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

문제

문제

출처

ICPC

왜 백트래킹할때 메인함수에서 시작하는지??

kng0258 3년 전 1

sait2000 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말