글 읽기 - C++소문난 칠공주 논리적 오류가 뭘까요??

blou888 2년 전 0

제가구현한 방식은

먼저 7명을 찾는데, 중간에 다른 사람들이 다 'S'라고 해도 조건이 충족이 안되면 그 자리에서 return을 하게 만들었고,

사람들의 좌표를 각각 벡터에 담고, 방문 배열을 바꿔주고,
7명에, 공주를 4명 이상 찾았으면, 각각 방문배열을 통해 인접 해 있는지, BFS를 돌렸고, 그 다음 각각 좌표를 담은 벡터를 통해 둘의 차이가 7이 안넘도록 (넘으면 return을 해 주었습니다) 해 주었습니다.

그런데 혹시 제 답에 어떤 반례가 있는지 알 수 있습니까?

아니면 어느 부분이 논리적으로 틀렸는지 지적좀 부탁드립니다!

/*
* 백트래킹으로 7개를 찾고
* 4명 이상인지 판별해서
* 4명 이상이면 벡터에 담아둔 모든 좌표들과 비교해서
* 차이가 가장 큰 게 7 이상 난다면, X
* 7이하라면 cnt++
*/

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

char arr[6][6];
int cnt;
vector<pair<int, int>> v;
bool is_visit[6][6];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

void findPrince(int x, int y, int deep, int prince) {
	if (deep == 7) {
		if (prince < 4) return;
		else {
			//이어져 있는지 없는지 확인 해야 함.
			int connect = 6;
			queue<pair<int, int>> Q;
			Q.push({ v[0].first,v[0].second });
			is_visit[Q.front().first][Q.front().second] = false;
			while (!Q.empty()) {
				int i = Q.front().first;
				int j = Q.front().second;
				Q.pop();

				for (int k = 0; k < 4; k++) {
					int tx = i + dx[k];
					int ty = j + dy[k];
					if (tx >= 0 && tx < 5) {
						if (ty >= 0 && ty < 5) {
							if (is_visit[tx][ty]) {
								connect--;
								Q.push({ tx,ty });
								is_visit[tx][ty] = false;
							}
						}
					}
				}
			}
			if (connect != 0) {
				//방문 했던 것을 다시 표시를 해 준다.
				for (int i = 0; i < 7; i++) is_visit[v[i].first][v[i].second] = true;
				return;
			}

			//모든 좌표의 차이가 7이하여야 함.
			for (int i = 0; i < v.size() - 2; i++) {
				for (int j = i + 1; j < v.size() - 1; j++) {
					if (abs(v[i].first - v[j].first) + abs(v[i].second - v[j].second) > 7) {
						//두 좌표의 차이가 7 보다 크다면,
						return;
					}
				}
			}
			//다 7보다 작다면,
			cnt++;
			return;
		}
	}//아직 공주를 7명을 다 뽑는다고 하더라도 4명이 안된다면 리턴
	else if (7 - deep < 4 - prince) return;
	for (int i = x; i < 5; i++) {
		int j = 0;
        //다음 열 부터 계산 하기 위해서 x==i를 넣어주었음.
		if (x == i) j = y + 1;
		for (; j < 5; j++) {
            //이 지점을 방문했다는 is_visit배열과, 벡터에 담기
			is_visit[i][j] = true;
			v.push_back({ i,j });
			if (arr[i][j] == 'S') {//자리가 'S'라면 공주+1 을 해서 재귀.
				findPrince(i, j, deep + 1, prince + 1);
			}
			else {//자리가'Y'라면 prince는 그대로.
				findPrince(i, j, deep + 1, prince);
			}
            //백트래킹 하면서 다시 벡터 뺴 주고 방문도 취소 해 주고
			v.pop_back();
			is_visit[i][j] = false;
		}
	}
	return;
}

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

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			is_visit[i][j] = true;
			v.push_back({ i,j });
			if (arr[i][j] != 'S') {
				findPrince(i, j, 1, 0);
			}
			else findPrince(i, j, 1, 1);
			v.pop_back();
			is_visit[i][j] = false;
		}
	}

	cout << cnt << "\n";

	return 0;
}

blou888 2년 전 0

51번째 줄, visit을 if문 밖에서 돌려주니 AC 받았습니다!

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

문제

문제

출처

ICPC

C++소문난 칠공주 논리적 오류가 뭘까요??

blou888 2년 전 0

blou888 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말