글 읽기 - 이분 매칭 메모리 초과 질문입니다.

(追記) (追記ここまで)

이분 매칭 메모리 초과 질문입니다.

2414번 - 게시판 구멍 막기

rkdxowhd98 5년 전 0

이분 매칭이라 생각해서 풀어봤습니다.

메모리 초과가 일어날 부분이 없는거 같은데 고수님들 도와주십시오 ᅲᅲ

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n, m;
vector<string> board;
vector<vector<int>> graph;
int visitCount;
vector<int> isChecked, isVisited;
bool dfs(int index) {
 if(visitCount == isVisited[index]) {
 return false;
 }
 isVisited[index] = visitCount;
 for(int &next : graph[index]) {
 if(isChecked[next] == -1 || dfs(isChecked[next])) {
 isChecked[next] = index;
 return true;
 }
 }
 return false;
}
int binmatch() {
 isChecked.assign(graph.size(), -1);
 isVisited.assign(graph.size(), -1);
 int ans = 0;
 for(int i = 0;i < graph.size();++i) {
 visitCount = i;
 ans += dfs(i);
 }
 return ans;
}
int main() {
 ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 cin >> n >> m;
 board.resize(n);
 for(string &str : board) {
 cin >> str;
 }
 int l = 0;
 vector<vector<int>> left(n, vector<int> (m, -1));
 for(int i = 0;i < n;++i) {
 for(int j = 0;j < m;++j) {
 if(board[i][j] == '*' && left[i][j] == -1) {
 for(int k = j;k < m;++k) {
 if(board[i][k] == '*') {
 left[i][k] = l;
 }
 else {
 break;
 }
 }
 ++l;
 }
 }
 }
 int r = 0;
 vector<vector<int>> right(n, vector<int> (m, -1));
 for(int j = 0;j < n;++j) {
 for(int i = 0;i < m;++i) {
 if(board[i][j] == '*' && right[i][j] == -1) {
 for(int k = i;k < n;++k) {
 if(board[k][j] == '*') {
 right[k][j] = r;
 }
 else {
 break;
 }
 }
 ++r;
 }
 }
 }
 graph.resize(l);
 for(int i = 0;i < n;++i) {
 for(int j = 0;j < m;++j) {
 if(board[i][j] == '*') {
 graph[left[i][j]].push_back(right[i][j]);
 }
 }
 }
 cout << binmatch() << "\n";
}

hunni10 5년 전 1

1. 72줄, 73줄 오타

2. 다음 입력

4 4

**..

..**

**..

..**

에서 항상 벡터 out of range 오류가 발생하는데 l = 4이고 r=8 인데 dfs에서 isChecked[next]하면서 문제가 생길거라고 봄

3. 문제는 메모리 초과인데, 최악의 경우, 즉 구멍이 격자 단위로 나 있다면 graph의 크기는 1,250가 되고 각 벡터당 원소가 하나씩 들어있다고 상정해도

벡터 자체의 크기 12바이트, 원소의 크기 4바이트로 graph의 크기는 16 * 1,250 = 20,000바이트 = 20KB 밖에 안됨

isChecked나 isVisited도 고려해도 40 * 1,250 = 50KB

사실 메모리 초과가 없더라도 오답이 나와야 했는데, 메모리 초과라고 뜬 이유는 저도 잘 모르겠네요.

//줄 72 부터
//for(int j = 0;j < n;++j) { 
// for(int i = 0;i < m;++i) {
// if(board[i][j] == '*' && right[i][j] == -1) {
// j : m, i : n이 의도된 것으로 보임
for(int j = 0;j < m;++j) { 
 for(int i = 0;i < n;++i) {
 if(board[i][j] == '*' && right[i][j] == -1) {
 ...
 }
 }
} 
//입력 left right
//4 4 
//**.. 00.. 01.. 
//..** ..11 ..23
//**.. 22.. 45..
//..** ..33 ..67

rkdxowhd98 5년 전 0

좋은 답변 감사합니다.

지적한 부분 수정하니까 통과했습니다.

그런데 런타임에러나 틀렸습니다가 아닌 메모리 초과는 왜인지 여전히 모르겠네요

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

이분 매칭 메모리 초과 질문입니다.

rkdxowhd98 5년 전 0

hunni10 5년 전 1

rkdxowhd98 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말