글 읽기 - 30~40퍼센트 사이에 틀렸습니다가 뜹니다 반례가 있을까요??

kiasu93 5년 전 0

질문을 위해 코드에 주석처리를 했습니다

기본적으로 dfs 탐색을 이용하여 벽을 설치할 위치를 3개 선택하고

3개가 선택되는 순간마다 바이러스확장을 위해 bfs탐색을 했습니다

뭔가 잘못되었는지 30퍼센트에서 조금더 올라가다가 틀렸습니다가 뜨네요 ㅠ

일단 예제는 모두 맞는 출력값이 나옵니다

반례가 있을까요???

#include<iostream>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;

typedef struct loc {
	int x;
	int y;
};
loc lc;
queue<loc> que; // 초기 바이러스 위치를 담을 큐
queue<loc> que_copy; // 벽이 3개 세워지는 순간마다 초기화되어 바이러스를 확장시키는데 이용될 복사본큐

int n, m;
int arr[10][10]; // 초기상태이자 벽을 설치할 배열
int arr_copy[10][10]; // 벽이 3개 세워지는 순간마다 초기화되어 바이러스를 확장시킬 복사본배열
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int safe;
int result;

void init() {
	que_copy = que; // 초기 바이러스 상태로 copy를 초기화
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			arr_copy[i][j] = arr[i][j]; // 벽이 3개세워진(바이러스는 지워진) 상태로 초기화
		}
}
void dfs(int a, int b, int wall) {
	
	if (a == n - 1 && b == m - 1) // 2차원 배열의 경계
		return;

	if (wall == 3) { // 벽이 3개세워지면
		init(); // 바이러스가 들어있는 que_copy와  벽이3개세워진 arr로 arr_copy를 초기화
		while (!que_copy.empty()) {
			int x1 = que_copy.front().x;
			int y1 = que_copy.front().y;
			que_copy.pop();

			for (int i = 0; i < 4; i++) {
				if (x1 + dx[i] >= 0 && x1 + dx[i] < n && y1 + dy[i] >= 0 && y1 + dy[i] < m && arr_copy[x1 + dx[i]][y1 + dy[i]] == 0) {
					// 경계 내에서 4방향탐색을 하여 0이라면 바이러스범위 확장
					lc.x = x1 + dx[i];
					lc.y = y1 + dy[i];
					arr_copy[lc.x][lc.y] = 2; // 바이러스로 바꿔준다
					que_copy.push(lc);
				}
			}		
		} // 바이러스범위 확장 끝
		int temp = 0; 
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr_copy[i][j] == 0)
					temp++; // 바이러스 bfs 탐색이 끝난뒤 안전구역 카운팅
			}
		}
		safe = temp;
		result = max(result, safe); // 매번 벽이3개가 되어 바이러스 bfs탐색을 마치면 안전구역이 넓은 케이스로 
		return;						// result값을 초기화
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) {
				arr[i][j] = 1;
				dfs(i, j, wall + 1);
				arr[i][j] = 0; // 재귀호출 및 백트레킹
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];

			if (arr[i][j] == 2) {
				lc.x = i;
				lc.y = j;
				que.push(lc); // que에 바이러스 초기 위치 삽입
			}
		}
	}	
	dfs(-1, -1, 0);
	cout << result << '\n';
	return 0;
}

AdcKi 5년 전 1

if (a == n - 1 && b == m - 1)
return;
이 코드를 주석처리하면 AC가 나옵니다. DFS돌릴때 작성하신 코드대로라면 굳이 좌표를 넘겨서 연산할게 없으니 돌리면 되고

wall이 3보다 크게 dfs돌수도 없고 for문으로 순회하기에 좌표를 벗어 나지도 않습니다.

만약 a,b 넘겨서 loop를 줄이고 싶다면 for문 초기값과 call값만 수정 해주면 되겠네요.

#include<iostream>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;

typedef struct loc {
	int x;
	int y;
};
loc lc;
queue<loc> que; // 초기 바이러스 위치를 담을 큐
queue<loc> que_copy; // 벽이 3개 세워지는 순간마다 초기화되어 바이러스를 확장시키는데 이용될 복사본큐

int n, m;
int arr[10][10]; // 초기상태이자 벽을 설치할 배열
int arr_copy[10][10]; // 벽이 3개 세워지는 순간마다 초기화되어 바이러스를 확장시킬 복사본배열
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int safe;
int result;

void init() {
	que_copy = que; // 초기 바이러스 상태로 copy를 초기화
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			arr_copy[i][j] = arr[i][j]; // 벽이 3개세워진(바이러스는 지워진) 상태로 초기화
		}
}
void dfs(int a, int b, int wall) {

	if (wall == 3) { // 벽이 3개세워지면
		init(); // 바이러스가 들어있는 que_copy와  벽이3개세워진 arr로 arr_copy를 초기화
		while (!que_copy.empty()) {
			int x1 = que_copy.front().x;
			int y1 = que_copy.front().y;
			que_copy.pop();

			for (int i = 0; i < 4; i++) {
				if (x1 + dx[i] >= 0 && x1 + dx[i] < n && y1 + dy[i] >= 0 && y1 + dy[i] < m && arr_copy[x1 + dx[i]][y1 + dy[i]] == 0) {
					// 경계 내에서 4방향탐색을 하여 0이라면 바이러스범위 확장
					lc.x = x1 + dx[i];
					lc.y = y1 + dy[i];
					arr_copy[lc.x][lc.y] = 2; // 바이러스로 바꿔준다
					que_copy.push(lc);
				}
			}		
		} // 바이러스범위 확장 끝
		int temp = 0; 
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr_copy[i][j] == 0)
					temp++; // 바이러스 bfs 탐색이 끝난뒤 안전구역 카운팅
			}
		}
		safe = temp;
		result = max(result, safe); // 매번 벽이3개가 되어 바이러스 bfs탐색을 마치면 안전구역이 넓은 케이스로 
		return;						// result값을 초기화
	}

	for (int i = a; i < n; i++) {
		for (int j = ( i == a ) ? b + 1 : 0 ; j < m; j++) {
			if (arr[i][j] == 0) {
				arr[i][j] = 1;
				dfs(i, j, wall + 1);
				arr[i][j] = 0; // 재귀호출 및 백트레킹
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];

			if (arr[i][j] == 2) {
				lc.x = i;
				lc.y = j;
				que.push(lc); // que에 바이러스 초기 위치 삽입
			}
		}
	}	
	dfs(0, -1, 0);
	cout << result << '\n';
	return 0;
}

kiasu93 5년 전 0

와...주석처리하니까 정말 되는군요 ..

그런데 어차피 for문으로 탐색하기때 문에 범위를 넘을 일이 없는데

왜 저 문장때문에 틀렸던 걸까요???

AdcKi 5년 전 1

wall의 값이 몇인지 상관없이 마지막에 dfs호출위치 -> 1을 넣은 위치가 배열의 마지막 값이면 무조건 종료됩니다.

그래서 배열의 마지막 값이 벽을 세워야 최적해가 나오는 상황이라면 해당 상황을 연산하지 않겠지요.

kiasu93 5년 전 0

친절한 댓글 정말 감사합니다 (꾸벅)

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

문제

문제

출처

ICPC

30~40퍼센트 사이에 틀렸습니다가 뜹니다 반례가 있을까요??

kiasu93 5년 전 0

AdcKi 5년 전 1

kiasu93 5년 전 0

AdcKi 5년 전 1

kiasu93 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말