글 읽기 - 도와주세요

gussh03 5년 전 0

틀린이유를 모르겠네요ㅠㅠ 도와주세요

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

int mapSize, arr[102][102], visited[102][102];
int dx[] = { 0, 1, 0, -1 }, dy[] = { -1, 0, 1, 0 };
int maxNum = -987654321;
void dfs(int y, int x, int depth, int sum);
void check();
int main() {
	int count = 1;
	while (1) {
		cin >> mapSize;
		if (mapSize == 0)
			break;
		for (int i = 0; i < mapSize; i++) {
			for (int j = 0; j < mapSize; j++) {
				cin >> arr[i][j];
			}
		}
		for (int y = 0; y < mapSize; y++) {
			for (int x = 0; x < mapSize; x++) {
				visited[y][x] = 1;
				dfs(y, x, 1, arr[y][x]);
				visited[y][x] = 0;
			}
		}
		memset(visited, 0, sizeof(visited));
		check();
		cout << count << ". " << maxNum << endl;
		count++;
		maxNum = -987654321;
	}
	return 0;
}
void dfs(int y, int x, int depth, int sum) {

	if (depth == 4) {
		maxNum = max(sum, maxNum);
		return;
	}
	for (int i = 0; i < 4; i++) {
		int tmpx = x + dx[i];
		int tmpy = y + dy[i];
		if (tmpx < 0 || tmpy < 0 || tmpx >= mapSize || tmpy >= mapSize || visited[tmpy][tmpx] == 1)
			continue;
		visited[tmpy][tmpx] = 1;
		dfs(tmpy, tmpx, depth + 1, sum + arr[tmpy][tmpx]);
		visited[tmpy][tmpx] = 0;
	}
}
void check() {
	for (int y = 0; y < mapSize; y++) {
		for (int x = 0; x < mapSize; x++) {
			if (x - 1 >= 0 && y - 1 >= 0 && y + 1 < mapSize) { // ㅓ
				maxNum = max(maxNum, arr[y][x] + arr[y - 1][x] + arr[y + 1][x] + arr[y][x - 1]);
			}
			if (x - 1 >= 0 && x + 1 < mapSize && y + 1 < mapSize) { // ㅜ
				maxNum = max(maxNum, arr[y][x] + arr[y + 1][x] + arr[y][x - 1] + arr[y][x + 1]);
			}
			if (y - 1 >= 0 && x + 1 < mapSize && y + 1 < mapSize) { // ㅏ
				maxNum = max(maxNum, arr[y][x] + arr[y - 1][x] + arr[y + 1][x] + arr[y][x + 1]);
			}
			if (y - 1 >= 0 && x - 1 >= 0 && x + 1 < mapSize) { // ㅗ
				maxNum = max(maxNum, arr[y][x] + arr[y - 1][x] + arr[y][x + 1] + arr[y][x - 1]);
			}
		}
	}
}

st4889 5년 전 2

dfs로 돌리면 4개의 블록으로 만들수 있는 모든 경우의 테트리스를 탐색하게 됩니다.

하지만 문제를 보면 4개로 만들수 있는 모든 경우가 아니라, 그 중 5개만 탐색하게 됩니다.

예를들어 ┐ 모양은 있고 ┌ 이 모양은 없습니다.

그래서 dfs로 하면 안되고 각 모양별로 배열에 입력해놓는 식으로 정해놓고 탐색해야합니다.

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

문제

문제

출처

ICPC

도와주세요

gussh03 5년 전 0

st4889 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말