글 읽기 - ㅗ 모양 어떻게 찾아야 하나요?

dragonite 6년 전 0

지금 문제를 풀긴했는데,

ㅗ 모양에 대해서 어떻게 푸는지 모르겠습니다.

현재 코드는 배열에 -1 인덱스가 들어가면 0으로 인식되서 풀리긴 하는데,

원래 컴파일러가 배열 바깥의 인덱스에 대해서는 0으로 인식하는 것인가요?

ㅗ 모양을 찾기 위한 아이디어가 무엇인가요?

/*
16:33
테트로미노 시작

1. ㅗ 모양의 최대합 기능
2. 나머지 모양 최대합 기능.
3. 위 의 두 개 중에 큰 값을 출력
*/

#include <iostream>
#include <algorithm>
using namespace std;

#define SIZE 5 // 505
int map[SIZE][SIZE];
int visit[SIZE][SIZE];
int maxVal;
int N, M;
int x, y;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int minVal = 2123456789;

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

void dfs(int depth, int cx, int cy, int sum) {

	if (depth == 4) {
		maxVal = max(maxVal, sum);
		return;
	}

	for (int i = 0; i < 4; i++) {
		int nx = cx + dx[i];
		int ny = cy + dy[i];
		if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
		if (visit[nx][ny] == 0) {
			visit[nx][ny] = 1;
			dfs(depth + 1, nx, ny, sum + map[nx][ny]);
			visit[nx][ny] = 0;
		}
	}
	visit[cx][cy] = 0;
}

void star_dfs(int x, int y) {

	if (x == 0 && y == 0) return;
	if (x == (N - 1) && y == (M - 1)) return;
	if (x == 0 && y == (y == M - 1)) return;
	if (x == (N - 1) && y == 0) return;

	int sum2 = 0;
	minVal = 2123456789;
	sum2 += map[x][y] + map[x][y + 1] + map[x][y - 1] + map[x + 1][y] + map[x - 1][y];
	minVal = min(minVal, map[x][y + 1]);
	minVal = min(minVal, map[x][y - 1]);
	minVal = min(minVal, map[x + 1][y]);
	minVal = min(minVal, map[x - 1][y]);
	sum2 -= minVal;

	maxVal = max(maxVal, sum2);
	return;
}


void solve() {

	// 4가지 모양
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visit[i][j] = 1;
			dfs(1, i, j, map[i][j]);
			visit[i][j] = 0;
		}
	}

	// 별표에서 가장 작은 가장 자리를 하나 뺌.
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			star_dfs(i, j);
		}
	}
}

int main() {
	problemIn();
	solve();
	cout << maxVal << endl;
	return 0;
}

djm03178 6년 전 1

DFS로 찾으려면 그 모양은 조금 예외적으로 찾아줘야 합니다. 방법이야 여럿 있겠죠.

그리고 배열 인덱스를 벗어난 값은 그 어떤 값이 될지도 예측할 수 없고, 런타임 에러가 날 수도 있습니다. 0으로 인식된 건 순전히 운이 좋아서입니다.

dragonite 6년 전 0

아

감사합니당~~ 한번 찾아서 풀어보겠습니다!!!

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

문제

문제

출처

ICPC

ㅗ 모양 어떻게 찾아야 하나요?

dragonite 6년 전 0

djm03178 6년 전 1

dragonite 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말