글 읽기 - 저는 메모이제이션을 이용하여 문제를 해결하려고 하는데 접근이 이상한가요?

sm32289 1년 전 0

메모이제이션을 이용하여 문제를 해결하려고 하는데 혹시 접근 방법에 오류가 있는지 궁금합니다.

여러가지 테스트 케이스를 구해서 풀어봤을 때 답은 정상적으로 나왔으나 제출 시 바로 틀렸다는 문구가 나오네요.

저의 접근 방법이 잘못됐다면 댓글 부탁 드립니다!

#include <iostream>
#include<queue>
#include<string.h> 
using namespace std;
int a, b;
int input[1000][1000];
int answer[1000][1000];
int dp[1000][1000][2];//그룹이름 개수
int pp[1000000];
bool visit[1000][1000] = { 0 };
queue <int> Q;
int counts;
int name = 0;
int BFS(int y, int x, int name) {//0개수 세기
	if (y < 0 || x < 0 || x>=b || y>=a || visit[y][x]==true)return 0;
	dp[y][x][0] = name;
	int &ret = dp[y][x][1];
	
	if (ret != -1)return ret;
	ret = 1;//초기화
	visit[y][x] = true;
	if (input[y-1][x] == 0) {//위
		
		ret += BFS(y - 1, x, name);
		visit[y - 1][x] = true;
	}
	if (input[y][x - 1] == 0) {//좌

		ret += BFS(y, x - 1, name);
		visit[y][x - 1] = true;
	}
	if (input[y][x + 1] == 0) {//우

		ret += BFS(y, x + 1, name);
		visit[y][x + 1] = true;
	}
	if (input[y + 1][x] == 0) {//하

		ret += BFS(y + 1, x, name);
		visit[y + 1][x] = true;
	}

	return ret;
}


int main() {
	memset(dp, -1, sizeof(dp));
	cin >> a >> b;
	/*
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			scanf_s("%1d", &input[i][j]);
		}
	}*/
	for (int i = 0; i < a; i++) {
		string Inp;
		cin >> Inp;
		for (int j = 0; j < b; j++) {
			input[i][j] = Inp[j] - '0';
		}
	}
	
	for (int i = 0; i < a; i++) {//0을 추려내서 그룹을 만들자
		for (int j = 0; j < b; j++) {
			if (input[i][j] == 0 && visit[i][j]==false) {
				pp[name] = BFS(i, j, name);
				name++;
			}
			else {
				dp[i][j][1] = 0;
			}
		}
	}
	//그룹에 값을 넣어주자
	for (int i = 0; i < a; i++) {
		for(int j=0; j<b; j++){
		if (dp[i][j][0] == -1)continue;
		dp[i][j][1] = pp[dp[i][j][0]];
		}
	}
	//답 구하기
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			if (input[i][j] == 1) {
				counts = 1;
				int check[3] = { -1, -1, -1 };//c초기화
				if (dp[i + 1][j][1] > 0 && i<a-1) {
					counts += dp[i + 1][j][1];
					check[0] = dp[i + 1][j][0];
				}
				if (dp[i][j + 1][1] > 0 && j<b-1 && dp[i][j+1][0] != check[0]) {
					counts += dp[i][j + 1][1];
					check[1] = dp[i][j + 1][0];
				}
				if (dp[i - 1][j][1] > 0 && i>0 && dp[i - 1][j][0] != check[0] && dp[i - 1][j][0] != check[1]) {
					counts += dp[i - 1][j][1];
					check[2] = dp[i - 1][j][0];
				}
				if (dp[i][j - 1][1] > 0 && j>0 && dp[i][j - 1][0] != check[0] && dp[i][j - 1][0] != check[1] && dp[i][j - 1][0] != check[2]) {
					counts += dp[i][j - 1][1];
				}
				answer[i][j] = counts;
			}
			else {
				answer[i][j] = 0;
			}
		}
	}

	/*
	//input 보기
	cout << "input 살펴보기\n";
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			cout << input[i][j];
		}
		cout << "\n";
	}
	
	//dp 보기
	cout << "dp 살펴보기\n";
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			cout << dp[i][j][0];
		}
		cout << "\n";
	}
	//dp 보기
	cout << "dp 살펴보기\n";
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			cout << dp[i][j][1];
		}
		cout << "\n";
	}
	*/
	
	//답 
	//cout << "답 살펴보기 " << endl;
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			cout << answer[i][j]%10;
		}
		cout << "\n";
	}

}

dongwondavid 1년 전 0

입력에 버그가 있네요

대부분의 ONLINE JUDGE는 입력이 빠르게 주어져서 중간에 어떤 연산을 하면 오류가 나는 경우가 많습니다.

그리고 짜신 코드는 dfs(깊이 우선 탐색) 코드인 것 같습니다.

제가 고쳐서 맞은 코드(#43079327)는 공개해 놓았습니다!

#include <iostream>
using namespace std;
int a, b;
int input[1000][1000], answer[1000][1000], dp[1000][1000], pp[1000000+1];
bool visit[1000][1000];

int DFS(int y, int x, int name) {}//0개수 세기

int main() {
    char Inp[1000][1000];
	cin >> a >> b;
	for (int i = 0; i < a; i++) {
		cin >> Inp[i];
	}
    for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) input[i][j] = Inp[i][j] - '0';
    }
	int name=1;
	for (int i = 0; i < a; i++) {}//0을 추려내서 그룹을 만들자
	for (int i = 0; i < a; i++) {}//답 구하기
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) cout << answer[i][j];
		cout << endl;
	}
    return 0;
}

dongwondavid 1년 전 0

제출목록 보니까 이미 푸셨네요;;;

그런데 저는 "#43079327 제출"은 입력과 분석을 따로 했는데 맞았습니다를 받고 "#43079189 제출"은 입력과 분석을 같이 했는데 틀렸습니다를 받았습니다.

"#43079189 제출" 방식으로 계속 입력과 분석을하셨는데도 맞으셨네요... 이유가 뭐죠?

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

문제

문제

출처

ICPC

저는 메모이제이션을 이용하여 문제를 해결하려고 하는데 접근이 이상한가요?

sm32289 1년 전 0

dongwondavid 1년 전 0

dongwondavid 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말