월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부, 패의 수가 가능한 결과인지를 판별하려고 한다. 다음은 가능한 결과와 가능하지 않은 결과의 예이다.
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 예제 1 가능한 결과 | 예제 2 가능한 결과 | 예제 3 불가능한 결과 | 예제 4 불가능한 결과 |
|---|
네 가지의 결과가 주어질 때 각각의 결과에 대하여 가능하면 1, 불가능하면 0을 출력하는 프로그램을 작성하시오.
첫째 줄부터 넷째 줄까지 각 줄마다 6개국의 결과가 나라별로 승, 무승부, 패의 순서로 빈칸을 하나 사이에 두고 18개의 숫자로 주어진다. 승, 무, 패의 수는 6보다 작거나 같은 자연수 또는 0이다.
입력에서 주어진 네 가지 결과에 대하여 가능한 결과는 1, 불가능한 결과는 0을 빈칸을 하나 사이에 두고 출력한다.
입력 1
5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4
4 1 0 3 0 2 4 1 0 1 1 3 0 0 5 1 1 3
5 0 0 4 0 1 2 2 1 2 0 3 1 0 4 0 0 5
5 0 0 3 1 1 2 1 2 2 0 3 0 0 5 1 0 4
출력 1
1 1 0 0
6개 국가에 대해 발생 가능한 경기 조합이 15개뿐이고, 각 경기에는 승무패 3가지 경우만 발생한다.
완전 탐색은 어렵고, 팀별로 승무패를 줄일 수 있는지 확인하면서 가능한 경우만 탐색한다.
완전 탐색을 시도했을 때, O(K^N)
N: 6C2, K: 3(승무패) 3^15번의 함수 호출을 진행하기 때문에 이것을 백트래킹을 통해 가지치기한다.
N: 6C2 구하기
M = list(combinations(range(6), 2))팀별로 승무패를 줄일 수 있는지 확인한다.
for info in [(0, 2), (1, 1), (2, 0)]:
r1, r2 = info
R[t1][r1] -= 1
R[t2][r2] -= 1
if R[t1][r1] >= 0 and R[t2][r2] >= 0:
dfs(d + 1)
R[t1][r1] += 1
R[t2][r2] += 1깊이가 15일 때 가능한지 판단한다.
if d == 15:
res = 1
if any([sum(r) for r in R]):
res = 0
return완전탐색인데 가지를 칠 조건식이 있는지 생각해보는 것이 좋아보인다.
import sys
input = sys.stdin.readline
from itertools import combinations
def dfs(d:int):
global res, R, M
if d == 15:
res = 1
if any([sum(r) for r in R]):
res = 0
return
t1, t2 = M[d]
for info in [(0, 2), (1, 1), (2, 0)]:
r1, r2 = info
R[t1][r1] -= 1
R[t2][r2] -= 1
if R[t1][r1] >= 0 and R[t2][r2] >= 0:
dfs(d + 1)
R[t1][r1] += 1
R[t2][r2] += 1
if __name__ == '__main__':
M = list(combinations(range(6), 2))
answer = []
for _ in range(4):
res = 0
r = list(map(int, input().split()))
R = [r[i:i + 3] for i in range(0, 16, 3)]
dfs(0)
answer.append(res)
print(*answer)- 처음에는 백트래킹 안하고 풀 수 있을 것 같았다.
- 여러가지 경우를 생각해보았지만 완벽하게 모든 경우의 수를 체킹을 어려울 것 같아 DFS로 완전 탐색을 해야겠다는 생각이 들었따.
- 경기를 할 수 있는 모든 조합 계산하여 game에 저장
- combinations 조합으로 모든 경우의수를 계산한다!
- solution 함수에서 재귀적으로 각 라운드를 순회하면서 res의 배열의 값을 빼면서 승,무,패의 값이 남아있따면 ans=0으로 초기화해 불가능한 경기라고 answerr에 저장
- 15라운드에서 모두 0이면 답 1로 변경
- 만약에 itertools 라이브러리가 제한되어있었다면 dfs를 잘 구현하면 될 것 같다.
from sys import stdin
from itertools import combinations
def solution(round):
global ans
if round == 15:
ans = 1
for sub in res:
if sub.count(0) != 3:
ans = 0
break
return
t1, t2 = game[round]
for x, y in ((0, 2), (1, 1), (2, 0)):
if res[t1][x] > 0 and res[t2][y] > 0:
res[t1][x] -= 1
res[t2][y] -= 1
solution(round + 1)
res[t1][x] += 1
res[t2][y] += 1
answer = []
game = list(combinations(range(6), 2))
# 백트래킹
for _ in range(4):
data = list(map(int, stdin.readline().split()))
res = [data[i:i + 3] for i in range(0, 16, 3)]
ans = 0
solution(0)
answer.append(ans)
print(*answer)