글 읽기 - 잘못된 부분이 어딘지 알 수 있을까요?

yeongjae8066 5년 전 0

테스크 케이스가 뜨문뜨문 맞고.. 도저히 몇시간을 생각해도.. 생각이 안나네요

dfs로 완전탐색을 했는데 대체 어느 부분에서 틀린걸까요?

혹시 놓친부분이 있나요?

#include <iostream>
#include <algorithm>

using namespace std;

int mat[10][10];
int person[3][20];
int n, k;
int ans;
int p[3];
bool visit[11];

bool chk_visit() {
	bool ok = true;

	for (int i = 1; i <= n; i++) {
		if (visit[i] == false) {
			ok = false;
			break;
		}
	}

	return ok;
}

void dfs(int u, int v, int cnt) { // 상대방1 상대방2 게임횟수
	if (p[0] == k && p[1] != k && p[2] != k) { // 지우가 k에 도달했을 때 
		ans = 1;
		return;
	}

	if (cnt == 20 || p[1] == k || p[2] == k) { // 20이 넘어가거나 다른 사람이 먼저 도달했을 때
		return;
	}

	if (chk_visit()) { // 모든 수를 다 사용했는데 k에 도달했지 못했다면 리턴
		return;
	}

	if (u != 0 && v != 0) { // 둘 중 하나라도 0이 아니라면
		if (mat[person[u][cnt]][person[v][cnt]] == 2) {
			p[u] += 1;
			dfs(u, 0, cnt + 1);
			p[u] -= 1;
		}
		else if (mat[person[u][cnt]][person[v][cnt]] == 1) {
			if (u == 1) {
				p[v] += 1;
				dfs(v, 0, cnt + 1);
				p[v] -= 1;
			}
			else if (v == 1) {
				p[u] += 1;
				dfs(u, 0, cnt + 1);
				p[u] -= 1;
			}
		}
		else {
			p[v] += 1;
			dfs(v, 0, cnt + 1);
			p[v] -= 1;
		}
	}
	else { // 하나라도 0이 있다면
		for (int i = 1; i <= n; i++) {
			if (visit[i] == true) continue;
			visit[i] = true;
			// u가 0이라면
			if (u == 0) {
				if (mat[i][person[v][cnt]] == 2) { // u가 이기는 게임
					p[0] += 1;
					int tmp_you = (v == 1) ? 2 : 1;
					dfs(0, tmp_you, cnt + 1);
					p[0] -= 1;
				}
				else {  // 비기거나 진다면
					int tmp_you = (v == 1) ? 2 : 1;
					p[v] += 1;
					dfs(v, tmp_you, cnt + 1);
					p[v] -= 1;
				}
			}

			// v가 0이라면
			if (v == 0) {
				if (mat[person[u][cnt]][i] == 0) { // v가 이기는 게임
					p[0] += 1;
					int tmp_you = (u == 1) ? 2 : 1;
					dfs(0, tmp_you, cnt + 1);
					p[0] -= 1;
				}
				else { // 상대방이 이기는 게임
					int tmp_you = (u == 1) ? 2 : 1;
					p[u] += 1;
					dfs(u, tmp_you, cnt + 1);
					p[u] -= 1;
				}
			}

			visit[i] = false;
		}
	}
	
}

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

	freopen("data.txt", "r", stdin);
	cin >> n >> k;

	// 0이면 i가 지고 2면 i가 이긴다
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> mat[i][j];
		}
	}

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < 20; j++) {
			cin >> person[i][j];
		}
	}

	ans = 0;
	dfs(0, 1, 0);
	
	cout << ans << '\n';

	return 0;
}

yeongjae8066 5년 전 0

?? person은 1 2 만 쓰는데 어느 부분에서 그런거죠?

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

문제

문제

출처

ICPC

잘못된 부분이 어딘지 알 수 있을까요?

yeongjae8066 5년 전 0

yeongjae8066 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말