글 읽기 - 예제들은 맞는데 어떤 부분이 논리적으로 부족한지 잘 모르겠습니다.

efefds 3년 전 0

DFS 로 세개의 벽을 세우고, 그 상태에서 FF를 통해 확산가능한 바이러스 구역을 계산하여 min을 갱신하는 방식을 구현하려 하였습니다.

최종 갱신된 min을 답에 활용하였구요.

다른 질문들에서 있는 테스트 케이스들도 다 맞는데 어떤 부분이 부족한 것인지 감이 오지 않습니다,

코드 첨부하였으니 확인하시고 부족한 점 조언 부탁드려요.

감사합니다:)

#if 1
#include <stdio.h>
#define BIG(a,b) ((a)>(b)? (a) : (b))
int R, C;
int map[10][10],visit[10][10];
int wall[3][2];
int dr[] = { -1,1,0,0 }, dc[] = { 0,0,-1,1 };
int cnt,vcnt,wcnt;
int virus[11][2];
int min = 0x7FFFFFFF;

void input(void) {
	scanf("%d %d", &R, &C);
	for (int i = 0;i < R;i++) {
		for (int j = 0;j < C;j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2) {
				virus[vcnt + 1][0] = i;  //바이러스 위치 저장
				virus[vcnt + 1][1] = j;
				vcnt++;
			}
			if (map[i][j] == 1)
				wcnt++;
		}
	}
}

void FF(int r, int c) {

	for (int i = 0;i < 4;i++) {
		int nr = r + dr[i];
		int nc = c + dc[i];

		if (nr < 0 || nc<0 || nr >= R || nc >= C)
			continue;
		if (visit[nr][nc] == 1)
			continue;
		if (map[nr][nc] == 1)
			continue;

		visit[nr][nc] = 1;
		cnt++;
		FF(nr, nc);
	}
}

void sol(void) {
	for (int i = 1;i <= vcnt;i++) {
		if (visit[virus[i][0]][virus[i][1]] != 0)  //원래 바이러스 있던 지점을 시작점
			continue;
		cnt++;
		visit[virus[i][0]][virus[i][1]] = 1;
		FF(virus[i][0], virus[i][1]);
	}
}

void erase(void) {
	for (int i = 0;i < R;i++) {
		for (int j = 0;j < C;j++) {
			if (visit[i][j] == 1) {
				visit[i][j] = 0;
			}
		}
	}
	cnt = 0;
}

void dfs(int n) {
	int big = BIG(R, C);

	if (n > 3) {
		// 계산하고 min 구하기
		sol();
		min = (cnt < min) ? cnt : min;
		erase();
		return;
	}

	for (int i = 0;i < R*C;i++) {
		if (map[i / big][i%big] == 1)
			continue;

		if (map[i / big][i%big] == 2)
			continue;

		map[i / big][i%big] = 1; // 벽세우기;

		dfs(n + 1);
		map[i / big][i%big] = 0; // 벽지우기;
	}
}

int main(void) {
	int ans;
	input();

	dfs(1);
	wcnt += 3;
	ans = R * C - wcnt - min;
	printf("%d", ans);
	return 0;
}
#endif 

shg9411 3년 전 1

dfs 내에서 행과 열 중 큰 수로 행/열을 구하셔서 틀립니다.

efefds 3년 전 0

for문 하나로 이차원 배열 표현하는 법을 연습하려했는데 잘못했나보네요ㅠㅠ 이중 for문으로 바꿨더니 accept 되었어요! 감사합니다:)

shg9411 3년 전 0

big이라는 변수 대신 C를 사용하시면 원하시는 방법일거에요

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

문제

문제

출처

ICPC

예제들은 맞는데 어떤 부분이 논리적으로 부족한지 잘 모르겠습니다.

efefds 3년 전 0

shg9411 3년 전 1

efefds 3년 전 0

shg9411 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말