월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부, 패의 수가 가능한 결과인지를 판별하려고 한다. 다음은 가능한 결과와 가능하지 않은 결과의 예이다.
네 가지의 결과가 주어질 때 각각의 결과에 대하여 가능하면 1, 불가능하면 0을 출력하는 프로그램을 작성하시오.
6개국의 대진표의 유효성을 검사하는 문제. 6개국의 대진은 총 15번 일어나고, 각 대진에서 (승, 패), (무, 무), (패, 승)의 총 3가지 경우의 수가 일어나므로 3^15번의 비교를 통해 가능한 대진을 전부 테스트해 볼 수 있다. 따라서 브루트포스로 유효성을 검사하는 전략이 유효하다.
search : 한 대진표의 모든 대진 여부를 시뮬레이션하며 벨리드 여부를 검사한다. BFS로 진행한다. 큐에서 현재 대진 순서와, 현재 대진에서 남은 승무패를 저장한 리스트를 꺼낸다. 그리고 (승, 패), (무, 무), (패, 승) 중 가능한 경우일 경우(남은 승무패가 있을 경우) 이를 반영하여 큐에 삽입한다. 만약 최종 인덱스에 도달했다면, 남은 승무패 리스트를 검사하여 유효성을 판별한다.
is_valid_winning : 앞선 search함수에서 승무패 리스트를 검사하는 함수이다. 0이 아닌 값이 존재한다면 승무패가 올바르지 않으므로 False를, 그렇지 않다면 True를 반환한다.
solve : 메인함수. 모든 초기 승무패 리스트에 대해 search를 호출하여 그 결과를 저장하고, 마지막에 그 결과를 출력한다.
풀이 코드
from collections import deque
bracket_list = [ (i, j) for i in range(5) for j in range(i+1, 6)]
def search(win_list) :
q = deque([[0, win_list.copy()]])
while q :
idx, cur_list = q.popleft()
if idx == 15 :
if is_valid_winning(cur_list) :
return 1
continue
a, b = bracket_list[idx]
for k in range(3) :
if cur_list[3*a+k] and cur_list[3*b+2-k] :
next_list = cur_list.copy()
next_list[3*a+k] -= 1
next_list[3*b+2-k] -= 1
q.append([idx+1, next_list])
return 0
def is_valid_winning(lst) :
for left in lst :
if left != 0 :
return False
return True
def solve() :
result = list()
for _ in range(4) :
win_list = list(map(int, input().split()))
result.append(search(win_list))
print(*result)
solve()
