글 읽기 - 예외테스트케이스나 혹시 코드 좀 확인해주세요 ㅜㅜ!

donghyun3363 6년 전 0

우선 틀렸습니다. 가 나왔구요.

배열의 N X M의 인덱스 별로 DFS 를 통하여 모든 케이스를 검증 하였습니다. (간단하게 주석 처리했습니다.)

또한 ㅗ ㅓ ㅏ ㅜ 의 케이스는 별도로 예외 처리했구요!

해당 INPUT 케이스 뿐 아니라 개인적으로 INPUT 케이스를 넣어서 해보았지만.. 정상적인 값이 나와서요!

DFS와 같은 경우 모든 케이스를 다 훑고 ㅗ ㅓ ㅏ ㅜ의 케이스도 처리하여 모든 케이스 잡았다고 생각했는데.. 왜 문제가 생겼는지 확인하기 어렵

네요. 혹시 예외 테스트 케이스가 있거나 코드에 잘못된 부분이 있는지 알 수 있을까요?

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int Map[500][500];            // 숫자 저장 배열
int Visit[500][500];          // 방문 배열
int N;
int M;
int doMax = 0;                // 최대값 저장 값
int dx[] = {1, 0, -1, 0};     // 하 우 상 좌 이동 케이스
int dy[] = {0 ,1, 0, -1};
 
int doDFS(int x, int y, int time, int sum)
{
	if (time == 4)                // 블럭 4개일 경우
	{
		if (doMax < sum)
			doMax = sum;
		return 0;
	}
	for (int i = 0; i < 4; i++)   // 좌 우 위 아래 dfs
	{
		if (Visit[x + dx[i]][y + dy[i]] != 1 && x + dx[i] >= 0 && x + dx[i] <= N && y + dy[i] >= 0 && y + dy[i] <= N)
		{
			Visit[x + dx[i]][y + dy[i]] = 1;
			sum += Map[x + dx[i]][y + dy[i]];
			time++;
			doDFS(x + dx[i], y + dy[i], time, sum);
			time--;
			Visit[x + dx[i]][y + dy[i]] = 0;
			sum -= Map[x + dx[i]][y + dy[i]];
			if (time == 2)        // ㅗ ㅜ ㅓ ㅏ 케이스 해결
			{
				if (Visit[x][y + 1] != 1 && Visit[x + 1][y] != 1 && x + 1 <= N && y + 1 < N)
				{
					sum = sum + Map[x][y + 1] + Map[x + 1][y];
					if (doMax < sum)
						doMax = sum;
					sum = sum - (Map[x][y + 1] + Map[x + 1][y]);
				}
				if (Visit[x][y + 1] != 1 && Visit[x - 1][y] != 1 && y + 1 <= N && x - 1 >= 0)
				{
					sum = sum + Map[x][y + 1] + Map[x - 1][y];
					if (doMax < sum)
						doMax = sum;
					sum = sum - (Map[x][y + 1] + Map[x - 1][y]);
				}
				if (Visit[x][y - 1] != 1 && Visit[x + 1][y] != 1 && y -1 >= 0 && x + 1 <=N)
				{
					sum = sum + Map[x][y - 1] + Map[x + 1][y];
					if (doMax < sum)
						doMax = sum;
					sum = sum - (Map[x][y - 1] + Map[x + 1][y]);
				}
			}
		}
	}
	return 0;
}

int main()
{
	freopen("sample_input.txt", "r", stdin);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
			cin >> Map[i][j];
	}

	for (int i = 0; i < N; i++)        // 배열의 해당 인덱스에 위치하는 모든 케이스 확인
	{
		for (int j = 0; j < M; j++)
		{
			Visit[i][j] = 1;
			doDFS(i, j, 1, Map[i][j]);
			Visit[i][j] = 0;
		}
	}
	cout << doMax << endl;
	return 0;
}

kdk8361 6년 전 0

범위를 한번 더 확인 해 보시는게 좋을거 같습니다.

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

문제

문제

출처

ICPC

예외테스트케이스나 혹시 코드 좀 확인해주세요 ㅜㅜ!

donghyun3363 6년 전 0

kdk8361 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말