글 읽기 - 뭐가 틀렸는지 모르겠네요....ㅜㅜ(c++)

ote2010 7년 전 0

뭐가 틀렸는지 모르겠네요... 직접 입력바꿔봐도 맞는거같은데..ㅠㅠ

//#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define min(x, y) x < y ? x : y
using namespace std;
int board[11][11];
int save[11][11];
int maxVal=0;
int N;
int cnt;
void painting(int x, int y);
void bishop(int i, int j);
void init();

void init()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			board[i][j] = save[i][j];
		}
	}
}

void painting(int x, int y) // 비숍을 둔 위치에서 대각선 방향에 모두 2로 만들어서 비숍을 못두게 만드는 함수
{
	int val = min(x, y);

	int i = x - val + 1;
	int j = y - val + 1;

	for (; i <= N && j <= N; i++, j++) // \ 방향으로 
	{
		board[i][j] = 2;
	}

	val = y - 1;

	i = x + val;
	j = y - val;

	for (; i >= 1 && j <= N && j >= 1; i--, j++) // / 방향으로
	{
		board[i][j] = 2;
	}
}

void bishop(int i, int j)
{
	cnt++;

	painting(i, j); // 비숍을 못두게 만들고

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (board[i][j] == 1) // 비숍을 둘 수 있는 위치를 발견하면
			{
				//cout << "x : " << i << " y : " << j << endl;
				bishop(i, j); // 비숍을 일단 둬봅니다
			}
		}
	}
}

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

	cin >> N;
	
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int val;
			cin >> val;
			board[i][j] = val;
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			save[i][j] = board[i][j];
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (board[i][j] == 1) // NxN 배열에 모두 비숍을 둬보고 cnt를 체크해서 max값을 찾습니다.
			{
				cnt = 0;
				//cout << "x : " << i << " y : " << j << endl;
				bishop(i, j);
				//cout << "cnt : " << cnt << endl;
				if (maxVal < cnt)
				{
					maxVal = cnt;
				}
				init(); // 처음 체스판으로 바꿔줍니다
			}
		}
	}

	cout << maxVal;

	return 0;
}

zlzmsrhak 7년 전 1

1. 39, 44번째 줄에서 i가 N을 넘어갈 수 있습니다.

2. 무슨 알고리즘으로 작성한 코드인지 모르겠지만, 백트래킹이라면 방법이 잘못되었습니다.

저 경우는, 전수조사를 하는 코드처럼 보이지만, 사실은

1) 모든 첫 비숍의 위치 N^2에 대하여,

2) 행이 가장 작은, 같은 경우 열이 가장 작은 위치에 비숍을 하나씩 놓아보기

입니다. 이런 식으로 처리하면 모든 경우를 처리할 수 없습니다.

반례입니다.

ote2010 7년 전 0

저.. 무슨 말씀이신지 조금 더 구체적으로 설명해주시면 안될까요?ㅠㅠ

백트래킹을 공부하면서 푼 문제이긴 합니다..ㅠㅠ 코드 알아보시기 어려우신거같아서 주석도 달았습니다..ㅠㅠ

그리구 반례로 들어주신거는 출력이 3 아닌가요?? 지금 저 코드에서 3 잘 나오는데..ㅠㅠ 아 그리고 지적해주신 i는 바꿨습니다 감사합니다

zlzmsrhak 7년 전 2

1. 제가 깜박하고 0과 1을 반대로 써놨네요.. 반례 다시 드릴게요. 답은 4입니다.

2. 코드는 알아봤는데 코드가 구현하려는 것이 무엇인지 예상이 안되서 코드가 하는 일을 적어놓은 것입니다.

구현하려는 알고리즘이 무엇인지 설명하지 않으면 구체적인 답변을 얻을 수 없겠죠.

단순히 저 코드만 보면 그리디 알고리즘처럼 생겼습니다.

3. 백트래킹은 "전수조사"가 목적이기 때문에, 재귀를 호출한 후 상태를 초기화 해 주어야 합니다.

105번째 줄에서 초기화를 한 것 처럼, 65번째 줄에서 함수가 끝날 때, 시작부분에서 놓아둔 비숍을 물리는 작업을 해야 합니다.

아마 이렇게 구현하면 시간초과가 날 가능성이 꽤 높은데, 시간초과가 나오면 다시 질문하세요.

ote2010 7년 전 0

아.....제가 완전 잘못짰네요ㅠㅠㅠㅠ 자세히 설명해주시고 반례도 찾아주셔서 정말 감사드립니다ㅠㅠ 다시 더 공부해보고 모르는 게 있으면 질문 올릴께요!!
감사합니다

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

문제

문제

출처

ICPC

뭐가 틀렸는지 모르겠네요....ㅜㅜ(c++)

ote2010 7년 전 0

zlzmsrhak 7년 전 1

ote2010 7년 전 0

zlzmsrhak 7년 전 2

ote2010 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말