글 읽기 - 왜 틀린 건지 모르겠어요.

eremo2002 6년 전 0

6중 for문으로 벽 3개를 설치하는 모든 경우의 수를 확인하고요. 각 경우마다 dfs를 통해서 바이러스를 끝까지 퍼뜨리고

그 이후 안전영역의 최대값을 구하는 방법으로 짜봤습니다.

값은 나오는데 정답이랑 틀려서요.

논리적으로 어디서 틀린 건지 못 찾겠어요 ㅠㅠ

조언 부탁드립니다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int arr[8][8];
bool check[8][8];
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
int cnt;
int res;
int n, m; //행 렬

void dfs(int x, int y) {
	check[x][y] = 1;

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

		if (0 <= nx && nx < n && 0 <= ny && ny < m) {
			//인접한 부분이 감염되었고   &&   다음 위치가 0이고   &&   다음 위치를 방문한 적이 없을 때
			if (arr[x][y] == 2 && arr[nx][ny] == 0 && check[nx][ny] == 0) {
				arr[nx][ny] = 2;
				dfs(nx, ny);
			}
		}
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;

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


	for (int i1 = 0; i1 < n; i1++) {
		for (int i2 = 0; i2 < m; i2++) {

			for (int i3 = 0; i3 < n; i3++) {
				for (int i4 = 0; i4 < m; i4++) {

					for (int i5 = 0; i5 < n; i5++) {
						for (int i6 = 0; i6 < m; i6++) {
							//6중 for문으로 벽3개를 모든 경우의 수로 설치해보기
							if (arr[i5][i6] == 0 && arr[i3][i4] == 0 && arr[i1][i2] == 0) {
								arr[i5][i6] = 1;
								arr[i3][i4] = 1;
								arr[i1][i2] = 1;


								//바이러스 퍼뜨리기
								for (int b = 0; b < n; b++) {
									for (int c = 0; c < m; c++) {
										dfs(b, c);
									}
								}

								//전염상황 끝난 후  안전영역 확인
								for (int b = 0; b < n; b++) {
									for (int c = 0; c < m; c++) {
										if (arr[b][c] == 0)
											cnt++;
									}
								}

								//안전영역의 최대값
								res = max(res, cnt);


								//설치했던 벽  기존 상태로 복구
								arr[i5][i6] = 0;
								arr[i3][i4] = 0;
								arr[i1][i2] = 0;

								

								//초기화
								cnt = 0;
								memset(check, false, sizeof(check));
							}


						}
					}
				}
			}
		}
	}


	cout << res;


	return 0;
}

kdk8361 6년 전 0

dfs 돌릴 때 arr값을 2로 변경한 후 복구를 해주셔야 합니다.

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

문제

문제

출처

ICPC

왜 틀린 건지 모르겠어요.

eremo2002 6년 전 0

kdk8361 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말