글 읽기 - 제 코드에 대체 무슨 문제가 있는건가요?

smucs13 4년 전 0

제가 완벽하다는 뜻이 아니라

이 로직이 왜 예제 케이스를 제대로 출력 못하는건지 도저히 모르겠습니다...

상단 좌측부터 시작해서 왼쪽대각선위와 오른쪽대각선위만 살피면서 비숍을 하나씩 놓으면 되는거 같은데

그런데 제 코드에서는 뭔가 왼쪽대각선과 오른쪽 대각선을 올바르게 살피고 있지 못한걸 저는 알고 있어요

근데 그 이유를 아무리 고민해봐도 모르겠습니다...

너무 짜증나서 미치겠어요 도와주세요

// https://www.acmicpc.net/problem/1799

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int MAX = 10;
int N, ans;
int MAP[MAX][MAX];
bool check[MAX][MAX];

// 0 : L, 1 : R
int dx[] = { -1,-1 };
int dy[] = { -1, 1 };

bool Left_Up(int x, int y) {

	int nx = x + dx[0];
	int ny = y + dy[0];
	while (true) {
		if (nx < 0 || ny < 0) return false;
		else if (check[nx][ny]) return true;

		nx += dx[0];
		ny += dy[0];
	}
}

bool Right_Up(int x, int y) {

	int nx = x + dx[1];
	int ny = y + dy[1];
	while (true) {
		if (nx < 0 || ny >= N) return false;
		else if (check[nx][ny]) return true;

		nx += dx[1];
		ny += dy[1];
	}
}


void show() {

	cout << "--------------------------" << '\n';
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << check[i][j] << ' ';
		}
		cout << '\n';
	}
}

void dfs(int x, int y, int cnt) {
	ans = max(cnt, ans);

	for (int i = x; i < N; i++) {
		for (int j = y; j < N; j++) {
			if (check[i][j] || MAP[i][j] == 0) continue;
			if (Left_Up(i, j) || Right_Up(i, j)) continue;
			check[i][j] = true;
			dfs(i, j, cnt + 1);
			check[i][j] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

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

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (MAP[i][j] == 0 || check[i][j]) continue;
			check[i][j] = true;
			dfs(i, j, 1);
			check[i][j] = false;
		}
	}

	cout << ans << '\n';
	return 0;
}

rhdqor213 4년 전 0

만약 N이 3이고 함수 dfs에 x,y의 값으로 1,2가 넘어왔다면 59, 60번째 줄에서 의도한 작동은 (1,2) (2,0) (2,1) (2,2) 일 것이라고 생각됩니다

하지만 60번째 줄에서 int j = y로 했기 때문에 실제 작동은 (1,2) (2,2) 가 되겠죠

예제 케이스부터 제대로 출력하지 못 하는 건 아마 이 부분에서 문제가 발생하는 것이 아닌가 싶습니다.

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

문제

문제

출처

ICPC

제 코드에 대체 무슨 문제가 있는건가요?

smucs13 4년 전 0

rhdqor213 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말