글 읽기 - 칠공주 질문이요

raisondet 8년 전 0

칠공주 문제.. 아래와 같이 풀었는데요.

접근 방법이 잘못 된건지... 틀렸다고 나옵니다.

문제를 푼 방법을 간단히 설명드리면

25개(5x5 배열) 중 7개를 고르는 조합 문제로 보고...

1. 25개 중 7개를 고른다. (시간에 걸리나요? ㅡㅡ)

2. 7개 중 임도연파가 4명 이상이면 return 0;

3. 7개 배열이 서로 연결되어 있으면 return 1;

이렇게 해서

return 된 값들을 count 했습니다.

#include <stdio.h>

int M = 25;
int N = 7;
int result[100];
char data[6][6];
int used[6][6];

int d[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };

void print() {
	int y = 0;
	int x = 0;

	for (int i = 0; i < N; i++) {
		//printf("%d ", result[i]);
		y = result[i] / 5;
		x = result[i] % 5;
		printf("%c", data[y][x]);
	}
	printf("\n");
}

int is_connected(int y, int x) {

	// 현재좌표가 상,하,좌,우 연결되어 있는지 확인
	for (int t = 0; t < 4; t++) {
		int ny = y + d[t][0];
		int nx = x + d[t][1];
		if (ny >= 0 && nx >= 0 && ny < 5 && nx < 5 && used[ny][nx] == 1) {
			return 1;
		}
	}
	return 0;
}

int f(int n, int pre) {
	// 7자리 조합 생성
	if (n == 0) {
		int imdo = 0;
		int y, x;

		// 초기화
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				used[i][j] = 0;
			}
		}

		// 7자리 조합이 서로 연결되어 있는지
		// 임도연파가 4명이상인지 확인
		for (int i = 0; i < N; i++) {
			y = result[i] / 5;
			x = result[i] % 5;

            // 임도연파가 4명 이상이면 return;
			if (data[y][x] == 'Y') imdo++;
			if (imdo > 3)
				return 0;
            
			// 상,좌 값과 연결되어 있는지 확인
			used[y][x] = 1;
			if (i == 0) {

			}
			else {
				// 연결되어 있지 않으면 return;
				if (!is_connected(y, x))
					return 0;
			}
		}
		//print();

		return 1;
	}

	// 25개 중 7자리 조합 생성
	int cnt = 0;
	for (int i = pre + 1; i < M; i++) {
		result[N - n] = i;
		cnt += f(n - 1, i);
	}

	return cnt;
}

int main() {

	for (int y = 0; y < 5; y++) {
		scanf("%s", &data[y]);
	}

	int cnt = f(N, -1);
	printf("%d", cnt);
	return 0;
}

yukariko 8년 전 0

제생각에는 방법은 괜찮으나 연결되어있는지 확인하는 과정에 문제가 있어보입니다.

현재의 코드에선 위치를 하나씩선택할때 숫자가 증가하는 방향으로 선택하는데, 이것이 항상 인접해있는것은 아닙니다.

예를들어 뽑은 위치가 0 2 5 6 7 이라고 가정해봅시다. 분명 0과 2는 5 6 7을 통해 이어져있지만, 위 코드에선 2를 검사할때 아무것도 연결되어있지 않다고 판단하여 종료될것입니다.

이런 경우는 used배열을 미리 체크한다음에 확인하는것이 좋습니다.

raisondet 8년 전 0

그러네요. ㅡㅡ;;;

감사합니다.

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

문제

문제

출처

ICPC

칠공주 질문이요

raisondet 8년 전 0

yukariko 8년 전 0

raisondet 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말