글 읽기 - 어떤 부분에서 틀렸는지 잘 모르겠습니다. 도움 부탁드립니다ㅠㅠ

wngywo12 5년 전 0

녹지 않은 점에 대해서 dfs를 한 번 실행해보고 방문하지 않은 지점이 있는지를 체크합니다.

방문하지 않은 지점이 있으면 두 덩어리 이상일 것이라는 방법으로 문제를 해결했습니다.

질문 게시판에 올라온 다른 테스트 케이스들은 모두 해결이 되는 상황입니다.

도움 부탁드립니다.

#include <iostream>
#include <cstring>

using namespace std;

int map[302][302];
bool visit[302][302];
int N, M;

void dfs(int x, int y);
void resolve(int(*ary)[302]);
int check(int row, int col, int(*ary)[302]);

int main()
{
	int i, j;
	int cnt = 0;
	bool result = true;
	memset(map, 0, sizeof(map));
	memset(visit, false, sizeof(visit));
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <M; j++)
		{
			if (i == 0 || i == N - 1 || j == 0 || j == M - 1) map[i][j] = 0;
			cin >> map[i][j];
		}
	}


	while (result) {
		resolve(map);
		cnt++;
		//printf("--------------------------------------------\n");
		/*
		for (i = 0; i < N; i++) {
			for (j = 0; j < M; j++) {
				cout << map[i][j];
			}printf("\n");
		}*/
        
        
		for (i = 1; i < N-1; i++) {
			for (j = 1; j < M - 1; j++) {
				if (map[i][j] != 0)break;
			}if (map[i][j] != 0)break;
		}//녹지 않은 부분을 찾음
		
		if (map[i][j] == 0) {
			cnt = 0;
			break;
		}
        
		dfs(i, j);
		//0도 아니고 visit이 false인 곳이 있으면 두 덩어리 이상을 의미
		for (i = 1; i < N - 1; i++) {
			for (j = 1; j < M - 1; j++) {
				if (map[i][j] != 0 && !visit[i][j]){
					result = false;
					break;
				}
			}
			if (!result)break;
		}
		memset(visit, false, sizeof(visit));
	}
	printf("%d\n", cnt);
    return 0;
}
void dfs(int x, int y) {
	if (!visit[x + 1][y] && x + 1 < N && map[x + 1][y] != 0) {
		visit[x + 1][y] = true;
		dfs(x + 1, y);
	}
	if (!visit[x - 1][y] && x - 1 < N && map[x - 1][y] != 0) {
		visit[x - 1][y] = true;
		dfs(x - 1, y);
	}
	if (!visit[x][y - 1] && y - 1 < N && map[x][y - 1] != 0) {
		visit[x][y - 1] = true;
		dfs(x, y - 1);
	}
	if (!visit[x][y + 1] && y + 1 < N && map[x][y + 1] != 0) {
		visit[x][y + 1] = true;
		dfs(x, y + 1);
	}
}
void resolve(int(* ary)[302]) {
	int i, j;
	int tmpMap[302][302];
	for (i = 1; i < N-1; i++) {
		for (j = 1; j < M-1; j++) {
			tmpMap[i][j] = check(i, j, map);
		}
	}
	for (i = 1; i < N - 1; i++) {
		for (j = 1; j < M - 1; j++) {
			map[i][j] -= tmpMap[i][j];
		}
	}

}
int check(int row, int col, int(*ary)[302]) {
	int resolveCnt = 0;
	if (row-1>=0&&ary[row - 1][col] <= 0) {
		resolveCnt++;
	}
	if (row+1<N&&ary[row + 1][col] <= 0) {
		resolveCnt++;
	}
	if (col-1>=0&&ary[row][col - 1] <= 0) {
		resolveCnt++;
	}
	if (col+1<M&&ary[row][col + 1] <= 0) {
		resolveCnt++;
	}
	if (resolveCnt > ary[row][col]) {
		resolveCnt = ary[row][col];
	}
	return resolveCnt;
}

wngywo12 5년 전 0

범위 수정하고 초기 visit한 것을 깜빡했습니다. 잘 안 되시는 분들은 범위 수정 한번 해보세요

// 2573.cpp: 콘솔 응용 프로그램의 진입점을 정의합니다.
//

#include "stdafx.h"
#include <iostream>
#include <cstring>

using namespace std;

int map[301][301];
bool visit[301][301];
int N, M;

void dfs(int x, int y);
void resolve(int(*ary)[301]);
int check(int row, int col, int(*ary)[301]);
int main()
{
	int i, j;
	int cnt = 0;
	bool result = true;
	memset(map, 0, sizeof(map));
	memset(visit, false, sizeof(visit));

	cin >> N >> M;
	for (i = 0; i < N; i++){
		for (j = 0; j <M; j++){
			cin >> map[i][j];
			if (i == 0 || i == N - 1 || j == 0 || j == M - 1) map[i][j] = 0;
		}
	}


	while (result) {
		resolve(map);
		cnt++;
		for (i = 0; i < N; i++) {
			for (j = 0; j < M; j++) {
				if (map[i][j] != 0)break;
			}if (map[i][j] != 0)break;
		}
		
		if (map[i][j] == 0) {//모두 0인 경우, 0을 출력
			cnt = 0;
			break;
		}
		visit[i][j] = true;
		dfs(i, j);
		//0도 아니고 visit이 false인 곳이 있으면 두 덩어리 이상을 의미
		for (i = 0; i < N; i++) {
			for (j = 0; j < M; j++) {
				if (map[i][j] != 0 && !visit[i][j]){
					result = false;
					break;
				}
			}
			if (!result)break;
		}
		memset(visit, false, sizeof(visit));
	}
	printf("%d\n", cnt);
    return 0;
}
void dfs(int x, int y) {
	if (!visit[x + 1][y] && x + 1 <= N -1 && map[x + 1][y] != 0) {
		visit[x + 1][y] = true;
		dfs(x + 1, y);
	}
	if (!visit[x - 1][y] && x - 1 >=0 && map[x - 1][y] != 0) {
		visit[x - 1][y] = true;
		dfs(x - 1, y);
	}
	if (!visit[x][y - 1] && y - 1 >= 0 && map[x][y - 1] != 0) {
		visit[x][y - 1] = true;
		dfs(x, y - 1);
	}
	if (!visit[x][y + 1] && y + 1 <= M - 1 && map[x][y + 1] != 0) {
		visit[x][y + 1] = true;
		dfs(x, y + 1);
	}
}
void resolve(int(* ary)[301]) {
	int i, j;
	int tmpMap[302][302];
	for (i = 1; i < N-1; i++) {
		for (j = 1; j < M-1; j++) {
			tmpMap[i][j] = check(i, j, map);
		}
	}
	for (i = 1; i < N - 1; i++) {
		for (j = 1; j < M - 1; j++) {
			map[i][j] -= tmpMap[i][j];
		}
	}

}
int check(int row, int col, int(*ary)[301]) {
	int resolveCnt = 0;
	if (row-1>=0&&ary[row - 1][col] <= 0) {
		resolveCnt++;
	}
	if (row+1<=N&&ary[row + 1][col] <= 0) {
		resolveCnt++;
	}
	if (col-1>=0&&ary[row][col - 1] <= 0) {
		resolveCnt++;
	}
	if (col+1<=M&&ary[row][col + 1] <= 0) {
		resolveCnt++;
	}
	if (resolveCnt > ary[row][col]) {
		resolveCnt = ary[row][col];
	}
	return resolveCnt;
}

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

문제

문제

출처

ICPC

어떤 부분에서 틀렸는지 잘 모르겠습니다. 도움 부탁드립니다ㅠㅠ

wngywo12 5년 전 0

wngywo12 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말