@@@ 알고리즘/백준 스터디

백준 17349(1루수가 누구야) - 해결

HTG 2022. 1. 18. 02:08
728x90

1루수가 누구야

 

문제

어느 무더운 여름날, 선린 야구부 앞으로 의문의 음료수가 도착했다!

"이거 마시고 힘내! - 1루수에게 😍"

선수들은 서로 자기가 1루수라며 누가 1루수다 아니다로 싸우기 시작했다. 총 9명이 싸우고 있는데, 9명 중  명이 거짓말을 하고 있는 것 같다! 선수들은 아래 중 하나를 주장하고 있다. (편의상 선수들은 1, 2, ..., 9의 등번호로 구분하자.)

  • 1 A: 선수 A가 1루수이다.
  • 0 A: 선수 A는 1루수가 아니다.

선수들의 설전을 지켜보던 감독님이 답답해서 한마디 했다.

"1루수가 누구야 2루수 이름이 뭐야 3루수는 몰라"

당신은 이제 '정확히 한 명이 거짓말을 하고 있다'는 가정과 '1루수는 정확히 한 명 존재한다'는 사실을 바탕으로 논리적 추론을 통해 특정 인물이 반드시 1루수라는 결론을 이끌어내야 한다. 학생들의 주장만으로 이러한 결론을 이끌어내는 것이 불가능할 수도 있다는 사실에 유의하자.

1루수가 누구야

 

입력

9개의 줄에 걸쳐, 각 줄마다 0 또는 1이 주어지고 A가 주어진다. (1 ≤ A ≤ 9)

 

출력

논리적 추론을 통해 1루수를 유일하게 특정할 수 있으면 해당 선수의 등번호를 출력한다.

1루수가 누군지 알 수 없다면 -1을 출력한다.


구현 문제라서 분기를 생각하였다.

일단은 전체다 탐색을 해야 하기 때문에 1~9까지 거짓말을 했을 경우를 다 파악하였다.

그리고 거짓말한 사람을 정했으면 1~9까지 말을 들어보고 판단하기

그렇게 해서 판단하는 기준은 다 탐색하였을 때 가능성 있는 사람이 1명이거나 가능성 없는 사람이 8명일 때,

1루수가 1명으로 특정된다.

이 과정에서 모순이 일어나는 경우를 제외해주었다.

하지만 틀린 경우가 하나 있었다. (90% 쯤에서 틀렸다)

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

out:
-1

이 경우 1 이 출력 되었는 데 그 이유는 가능성 있는 사람이 없고 가능성 없는 사람이 7명 이하일 경우 결과적으로 1명으로 특정할 수 가 없다.

이 경우 답을 도출할 수 없기 때문에 -1 인 경우를 추가해주었다.

import sys
input = sys.stdin.readline

# 사람을 저장 
# 숫자로 인덱스 받기위해 0 인덱스를 없애기 위해서
people = [-1]
for _ in range(9):
    num, A = map(int,input().split())
    people.append((num, A))

# 답이 될 수 있는 걸 다 담기 위해서
result = []
# 1~9번까지 거짓말 하는 사람
for i in range(1,10):
    # 1루수인사람을 찾기 위해
    num_list = [-1] * 10
    flag = 0
    # 1~9까지 확인
    for j in range(1,10):
        # 거짓말하는 사람이면 바꿔서
        if i == j :
            num, A = people[j]
            num = 1-num
        else:
            num, A = people[j]
        # 1이면 추가
        if num:
            # 이미 제외되었다면 모순이기 때문에
            # 다음 숫자로 넘어가기
            if num_list[A] == 0:
                flag = 1
                break
            num_list[A] = 1
        # 0이면 제외
        else:
            # 이미 추가되었다면 모순이기 때문에
            # 다음 숫자로 넘어가기
            if num_list[A] == 1:
                flag = 1
                break
            num_list[A] = 0
    # 모순이 일어나면 바로 다음으로
    if flag:
        continue
    
    # 다 순회하고나서 대상이 1명이라면 결과에 추가
    if num_list.count(1) == 1:
        result.append(num_list.index(1))
    # 아닌 대상이 8명이라면 나머지 한명 추가
    elif num_list.count(0) == 8:
        result.append(num_list.index(-1,1))
    # 1이 없다면 여러 명이 결과에 추가되기 때문에 
    # 이 경우는 결국 -1이기 때문에
    # re를 초기화하고 탐색을 종료
    elif 1 not in num_list:
        result = []
        break

# 다 돌고나서 결과가 1명이라면 그 한명이 정답
if len(set(result)) == 1:
    print(result[0])
# 없거나 여러명이라면 -1
else:
    print(-1)