백준 17349 1루수가 누구야

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

17349번: 1루수가 누구야

[주의할 조건]

정확히 한 명이 거짓말을 하고 있다.

정확히 한 명이 1루수로 정해지는 경우만 등번호를 출력한다.

 

[구하는 값]

1루수로 정해진 선수의 등번호

 

[생각의 흐름]

이런 논리적 흐름으로 결론을 도출하는 문제는 조건 하나가 주어지면

그 조건으로 결정되는 것들은 모두 체크를 해주어야 한다. (구슬찾기 문제가 생각난다..)

이 문제에선 여러 주장들을 처음에 주는데, 각각의 선수들이 거짓말을 하는 모든 경우를 계산해봐야 한다. 

 

그래서 나는 def()를 통해서 포문으로 

1번 선수가 거짓말을 했을 때-> 누가 1루수로 정해지는지 를 lie(1)로 반환.

2번 선수가 거짓말을 했을 때-> 누가 1루수로 정해지는지 를 lie(2)로 반환.

...

이 순서로 검사를 했다. 누가 거짓말을 하든 한 사람을 특정해야 하므로 

lie() 값이 바뀌면 def()는 -1로, 바뀌지 않고 무사히 종료되면 def()는 그 값으로 종료된다.

 

 

lie(i)는 다음과 같이 동작한다.

<1> i의 주장만 반대로 선수의 1루수 여부를 배열에 체크한다.(i가 누군가가 참이라고 주장했으면

나머지는 모두 1루수가 아니라는 체크도 해줘야 한다.)

<2>나머지 선수는 모두 참인 것을 가정하여 선수들의 1루수 여부를 배열에 체크한다.(마찬가지로, 참을 주장하는 경우 나머지가 모두 1루수가 아니라는 것을 체크해줘야 한다)

...

이 과정을 거치면서 lie(i)는 중간에 모순을 발견하거나, 모순 없이 완료가 된다.

 

//모순을 발견한 경우

<2>를 실행하는 도중에 x로 체크되어 있던 곳에 o를 체크해야하는 상황이 오거나 그 반대일 경우, 모순이다.

이런 경우에는 lie(i)를 -1로 나오고 쓸모없는 가정이라 무시하고 다음 lie를 계산한다

 

//모순이 없는 경우

모순없이 실행이 완료되었으면 누가 1루수로 모아졌는지 확인을 해야한다.  이때 선수들의 상태값은 참(o),거짓(x),미정(?)으로 존재한다. 다음이 그 예시이다.

 

oxxxxxx

oxx?xx?

?xxxxxx

 

o를 기준으로 생각하자.

 

o가 2개 이상 나오는 경우? 는 불가능하다. <2>를 실행하며 모순으로서 나갔을 것이다.

o가 1개인 경우? 지금은 이미 누가 거짓말을 하고 누가 진실을 얘기했는지 정해진 상태이기 때문에, 더이상 무언가가 거짓일 가능성은 생각하지 않으므로,그 o를 믿어도 된다. 1루수가 그 o로 정해진다.

o가 0개인 경우? 예를 들어서 모두의 주장이 '2번선수는 1루수가 아니다'일 경우이다. 정보가 하나밖에 없으므로 누군가를 o라고 할 수도 없지만 x라고 할 수도 없다. 즉 1,3,4...가 1루수일 가능성이 있는 것이다. 모순이 없었기 때문이 이 가능성은 유효하다. 이런 경우, 특정지을 수 있는 인물이 2명 이상이 되므로 이 경우 lie(i)를 넘어서 def()를 -1로 나와야한다. 

 

!!!누가 거짓말을 하든 1루수가 하나로 특정되어야 한다. 나는 이 부분을 착각해서 몇 번 틀렸었다!!!

 

 

다시 def()로 돌아와서,

 

모든 i=1,2,3,...에 대해서 lie(i)가 한 사람을 특정하면 그 값으로 답을 반환하고

 

어떤 lie(i)가 모순없이 두 사람 이상을 특정하면 -1로 값을 반환하고

 

어떤 lie(i)가 모순이면 그 값은 버려진다.

 

 

->코드가 좀 더럽다ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include<iostream> 
#include<cstring>
#include<vector>
using namespace std;
int rusu[10];
int talk[10][2];
int lie(int num);
int def();
int main() {

	freopen("Text.txt", "r", stdin);
	for (int i = 1; i <= 9; i++) {
		cin >> talk[i][0] >> talk[i][1];
	}
	
	cout << def();
	return 0;
}
int def() {
	int tmp;
	int ans = -1;
	for (int i = 1; i <= 9; i++) {
		memset(rusu, 0, sizeof(rusu));
		tmp = lie(i);

		if (tmp == -2)
			return -1;
		if (tmp >0 && ans == -1) {
			ans = tmp;
		}
		else if (tmp > 0 && ans>0) {
			if (ans == tmp)
				continue;
			else
				return -1;
		}
	}
	return ans;
}
int lie(int num) {

	if (talk[num][0] == 1)
		rusu[talk[num][1]] = -1;
	else {
		rusu[talk[num][1]] = 1;
		for (int i = 1; i <= 9; i++) {   //하나 결정되면 완벽히 차단...결정될 수 있는거 지금 다 결정한다는  뜻
			if(i!= talk[num][1])
				rusu[i] = -1;
		}
	}
	for (int i = 1; i <= 9; i++) {
		if (i == num)
			continue;
		if (talk[i][0] == 1) {
			if (rusu[talk[i][1]] == -1)
				return -1;
			rusu[talk[i][1]] = 1;
			for (int j = 1; j <= 9; j++) {
				if (j != talk[i][1]) {
					if (rusu[j] == 1)
						return -1;
					rusu[j] = -1;
				}
			}
		}
		else {
			if (rusu[talk[i][1]] == 1)
				return -1;
			rusu[talk[i][1]] = -1;
		}
	}
	vector<int> one;
	vector<int> zero;
	for (int i = 1; i <= 9; i++) {
		if (rusu[i] == 1)
			one.push_back(i);
		else if (rusu[i] == 0)
			zero.push_back(i);
	}

	if (one.size() == 1)
		return one[0];
	if(one.size()==0&&zero.size()==1)
		return zero[0];
	return -2;
}

 

 

 

 

in:
0 1
1 1
0 2
0 3
0 4
0 5
0 6
0 7
0 7
out:-1

 

이건 내가 틀렸을 때 유용했던 반례이다. 

 

 

문제가 참 생각할게 많고 귀찮다~~혹시나 답답해서 풀이를 찾고 있는 분께 도움이 되었기를..