글 읽기 - 14502 연구소 문제 답은 맞췄으나 이 두개의 코드 차이를 모르겠습니다.

skynet0149 6년 전 0

제일 처음 주석된 대로 하다가 대체 무엇이 문제인지 한참 찾다고 dfs함수에서 a, b를 그냥 받아오지말고 신경 써주지 않은 채

(1) for문에서 주석친대로 i와 j를 초기값을 1로 주고 그 안에서

map[i][j]=1;

cnt++;

dfs(i, j)

map[i][j]=0;

cnt--;

이런식으로 하고 dfs 맨 위와 아랫 부분 코드를 주석처리하니 돌아가더라구요... 원래 제 생각은 두개의 코드가 똑같다고 생각하는데...

(2) 그리고 i와 j에 dfs인 매개변수 dfs(i ,j) 이런식으로 준 다음 int i=a, int j=b 이거는 또 안되더라구요. 꼭 int i=1, int j=1로 하는 이유가 완전 탐색인 것 같은데... a, b로 받아도 완전탐색인거 같은데 계속 알듯 말듯 한데 정확한 이유를 잘 모르겠습니다...

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int N, M;
int map[9][9];
int cnt = 0;
int ans = -1;
int xdir[4] = { 0, 0, 1, -1 };
int ydir[4] = { 1, -1, 0, 0 };
int countMap() {
	int zero = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (map[i][j] == 0)
				zero++;
		}
	}
	return zero;
}
vector<pair<int, int>> wibar() {
	int i, j, k;
	vector<pair<int, int>> tmp;
	queue<pair<int, int>> q;
	for (i = 1; i <= N; i++)
		for (j = 1; j <= M; j++)
			if (map[i][j] == 2)
				q.push(make_pair(i, j));

	while (!q.empty()) {
		int nx = q.front().first;
		int ny = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int x = nx + xdir[i];
			int y = ny + ydir[i];
			if (x<1 || y<1 || x>N || y>M)
				continue;
			if (map[x][y] == 0) {
				map[x][y] = 2;
				tmp.push_back(make_pair(x, y));
				q.push(make_pair(x, y));
			}
		}
	}
	return tmp;
}
void dfs(int a, int b) {

	if (cnt == 3) {
		vector<pair<int, int>> tmp = wibar();
		int zero = countMap();
		if (zero > ans)
			ans = zero;
		int lenv = tmp.size();
		for (int i = 0; i < lenv; i++) {
			int x = tmp.back().first;
			int y = tmp.back().second;
			map[x][y] = 0;
			tmp.pop_back();
		}
	}
	else {
		for (int i = 1; i <= N; i++) {		//1을 a로
			for (int j = 1; j <= M; j++) {	//1을 b로
				if (map[i][j] == 0) {			//이 부분은 map[i][j]==0일 때 dfs(i, j)만 존재하면 안되려나요...
					map[i][j] = 1;
					cnt++;
					dfs(i, j);
					cnt--;
					map[i][j] = 0;
				}
			}
		}
	}
	/*if (state == 1) {
		map[a][b] = 0;
		cnt--;
		state = 0;
	}*/
}
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			scanf("%d", &map[i][j]);
	dfs(1, 1);
	printf("%d\n", ans);
	return 0;
}

djm03178 6년 전 2

i, j를 a, b로 초기화하고 돌리면 그 함수가 호출된 첫 줄에서는 올바르게 동작하지만, 그 다음 줄부터는 1열부터 시작해야 하는데도 또 b열부터 시작한다는 문제가 있습니다. 이 처리만 하면 완전탐색이 됩니다.

skynet0149 6년 전 0

정말 감사합니다 디버그로 찍어보면서 하는데 생각대로 잘 안되었는데 조언 감사드립니다. 좋은 하루 되세요

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

문제

문제

출처

ICPC

14502 연구소 문제 답은 맞췄으나 이 두개의 코드 차이를 모르겠습니다.

skynet0149 6년 전 0

djm03178 6년 전 2

skynet0149 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말