글 읽기 - 어디가 틀렸는지 잘 모르겠어요

choee9712 4년 전 0

일단 예제에 있는 것부터 입력해보고 있는데

예제 1, 2는 틀리고 예제 3은 맞고 ㅠㅠ

그냥 정답인 위치에 벽 세우고 DFS 돌리면 잘 돼서 DFS를 잘못한 건 아닌 거 같은데

어디가 틀린 걸까요?

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

int N, M;
int arr[9][9];
bool visited[9][9];
int maximum = 0;

void dfs(int i, int j) {
	visited[i][j] = true;

	if (j + 1 <= M)
		if (!visited[i][j + 1] && arr[i][j + 1] == 0) dfs(i, j + 1);

	if (j - 1 >= 1)
		if (!visited[i][j - 1] && arr[i][j - 1] == 0) dfs(i, j - 1);

	if (i + 1 <= N)
		if (!visited[i + 1][j] && arr[i + 1][j] == 0) dfs(i + 1, j);

	if (i - 1 >= 1)
		if (!visited[i - 1][j] && arr[i - 1][j] == 0) dfs(i - 1, j);
}

void wall(int i1, int j1, int cnt) {
    // 벽 세 개를 다 세웠으면
	if (cnt >= 3) {
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= M; j++)
                // 아직 방문하지 않은 노드 중 바이러스가 있는 위치부터 DFS
				if (!visited[i][j] && arr[i][j] == 2)
					dfs(i, j);

		int count = 0;
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= M; j++)
                // 방문하지 않았고, 바이러스가 퍼지지 않은 위치의 개수
				if (!visited[i][j] && arr[i][j] == 0)
					count++;

        // 최댓값 설정
		if (maximum < count)
			maximum = count;
        
        // 방문여부 초기화
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                visited[i][j] = false;

		return;
	}

    // 아직 벽 세 개보다 덜 세웠다면
	else {
		for (int i = i1; i <= N; i++) {
			for (int j = j1; j <= M; j++) {
                // 벽 세우기 완전탐색
				if (arr[i][j] == 0) {
					arr[i][j] = 1;
					wall(i, j, cnt + 1);
					arr[i][j] = 0;
				}
			}
		}
	}
}

int main() {
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			cin >> arr[i][j];

    // 벽 세우기 완전탐색
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (arr[i][j] == 0) {
				arr[i][j] = 1;
				wall(i, j, 1);
				arr[i][j] = 0;
			}
		}
	}

	cout << maximum;

	return 0;
}

djm03178 4년 전 1

지금 코드는 (i, j) 위치에 벽을 세웠으면 그 이후에는 그 오른쪽 아래 영역만 봅니다. 하지만 왼쪽 아래 부분도 보게 만들어야 합니다.

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

문제

문제

출처

ICPC

어디가 틀렸는지 잘 모르겠어요

choee9712 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말