글 읽기 - 어디가 틀렸는지 모르겠습니다. 도와주세요!

captureit 5년 전 0

먼저 DFS로 연결그래프를 찾은 다음에 그 연결그래프들을 이분매칭하는 방식으로 코드를 구현했는데 어디가 틀렸는지 잘 모르겠습니다..

애초에 이 방식으로는 풀 수 없는 문제인가요?..

/*
	 # 2414 : "게시판 구멍 막기"
*/

#include <iostream>
#include <memory.h>

#define MAX 101

using namespace std;

int n, m; // n : 행, m : 열  
int result; // 결과

char board[MAX][MAX]; // 게시판 정보 배열

int a[MAX][MAX], d[MAX]; // a : 연결정보, d : 선점정보

bool vis[MAX]; // 이분매칭 정점 방문여부

bool connected_vis[MAX][MAX]; // 연결그래프 정점 방문여부

int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

bool chkBoundary(int x, int y) {
	return (x >= 0 && y >= 0 && x < n && y < m);
}

void searchConnectedGraph(int x, int y) {

	if (!connected_vis[x][y]) {
		connected_vis[x][y] = true;
		a[x][y] = true;
	}


	for (int i = 0; i < 4; i++) {
		int newX = x + dy[i];
		int newY = y + dx[i];
		if (chkBoundary(newX, newY) && !connected_vis[newX][newY] && board[newX][newY] == '*') {
			connected_vis[newX][newY] = true;
			a[newX][newY] = true;
			searchConnectedGraph(newX, newY);
		}
	}
}

bool DFS(int vertex) {

	if (vis[vertex])
		return false;

	else
		vis[vertex] = true;

	for (int i = 0; i < m; i++) {
		if (a[vertex][i]) {
			if (d[i] == -1 || DFS(d[i]))
			{
				d[i] = vertex;
				return true;
			}
		}
	}

	return false;
}

int main() {

	memset(a, false, sizeof(a));
	memset(connected_vis, false, sizeof(connected_vis));
	fill(d, d + MAX, -1);

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!connected_vis[i][j] && board[i][j] == '*') {
				searchConnectedGraph(i, j);
				for (int i = 0; i < n; i++) {
					fill(vis, vis + MAX, false);
					if (DFS(i)) result++;
				}
			}
			fill(d, d + MAX, -1);
			memset(a, false, sizeof(a));
		}
	}

	cout << result << endl;
	return 0;
}

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

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠습니다. 도와주세요!

captureit 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말