용답노트

문제

• https://www.acmicpc.net/problem/6987

오답노트

• 첫 풀이
  • 제시된 월드컵 대진에서 팀별로 1씩 빼보는 방식으로 모든 경우를 탐색하여 그러한 대진표가 가능한지를 판단하려고 했음.
  • 해당 풀이대로 하면 팀별로(6) * 승무패에 대해서(3) * 다른 팀과 대진(6) 했을 경우에 수 에 대해서 뻴 수 있는게 있는지 모두 확인해보면서 최종적으로 15전 이 되었을 때 모두 0이 되는지 확인하기 때문에 (6*3*6)^15 라는 매우 큰 시간 복잡도를 가진다. 
  • 다만, (6*3*6)^15를 모두 확인하는 것은 아니고 1) 15전이 되지 않았더라도 뺄수 있는게 없으면 멈추고, 2)정답을 찾으면 바로 멈춘다 는 것을 고려해서 진행하였음.
  • 이렇게 할 경우, 입력으로 가능한 대진이 들어왔을 경우에는 금방 YES라고 출력하지만, 입력으로 불가한 대진이 들어올 경우에는 NO를 출력할 때까지 어마어마한 시간이 걸린다.
• 개선
  • 시간 복잡도를 대략으로라도 계산해보고, 15전이 되지 않아서 멈추는 경우의 수가 있다고 하더라도 너무 경우의 수가 많으니 다른 방법을 고안해 봤어야한다.
  •  1)15전이므로 모든 월드컵 대진에 대해서 3가지(승무패)에 대해서 탐색하되, 2)해당 대진이 주어진 입력과 요소가 하나라도 다르면 무조건 멈춤
  • 이렇게 하면 가능한 대진 and 요소와 일치하는것에 대해서만 탐색이 진행되기 때문에 훨씬 적은 시간 복잡도로 해결 가능(15개의 대전만 뽑아서 진행하기 때문에 이전 풀이에서 처럼 불가능한 대진에 대해서 탐색하는 시간이 자연스럽게 사라짐)

코드1(시간 초과)

import sys
sys.stdin=open("input.txt","rt") 
readl = sys.stdin.readline

def DFS(start, graph,matchCnt,ans,tc):
    if ans[tc]!=-1: return
    if matchCnt ==15:
        for i in range(6):
            if sum(graph[i]) > 0 :
                ans[tc]=0
                return
        ans[tc]= 1
        return
    for i in range(start, 6): #각 팀에 대해서 하나씩 빼보며 확인(앞팀부터 순차대로)
        for j in range(3): #승무패
            if graph[i][j] : #0이 아닌 경우에만
                graph[i][j]-=1
                for k in range(6): #본인 제외한 다른 5개팀에서 뺄수있는게 있는지 확인.
                    if i ==k: continue
                    #승무패 경우에 따라 나누기
                    if j == 0 :
                        if graph[k][2]: 
                            graph[k][2] -=1
                            DFS(start, graph, matchCnt+1, ans, tc)
                            graph[k][2] +=1
                    elif j == 1:
                        if graph[k][1]: 
                            graph[k][1] -=1
                            DFS(start, graph, matchCnt+1, ans, tc)
                            graph[k][1] +=1
                    elif j == 2:
                        if graph[k][0]: 
                            graph[k][0] -=1
                            DFS(start, graph, matchCnt+1, ans, tc)
                            graph[k][0] +=1
                graph[i][j]+=1
    return



ans = [-1,-1,-1,-1]
graph=[]
for tc in range(4):
    test = list(map(int, readl().split()))
    for cal in range(6):
        graph.append(test[3*cal:3*(cal+1)])
    for i in range(6):
        if sum(graph[i]) > 5 :
            break
    else:
        DFS(0, graph,0,ans, tc)
    graph=[]
    

print(*ans)

코드2 (정답)

import sys
import itertools
sys.stdin=open("input.txt","rt") 
readl = sys.stdin.readline

teamList =[0,1,2,3,4,5]
matchList = list(itertools.combinations(teamList,2))

#matchList = [ab ac ad ae af bc bd be bf ... ...]
#borad: graph와 일치하는지 확인을 위한 이중리스트
#matchCnt: 경기 진행 횟수, DFS가 끝나면 1이 추가됨. 15가 되는순간, 15번의 경기를 치룬 이후이므로 종료.
#tc: testcase number
def DFS(board,matchCnt,tc):
    if ans[tc] != -1:
        return
    if matchCnt == 15:
        ans[tc] = 1
        return
    team1 = matchList[matchCnt][0]
    team2 = matchList[matchCnt][1]

    #승,무,패 한 경우에 대해서
    for i in range(3): 
        board[team1][i] += 1
        board[team2][2-i] += 1 
        #graph와 일치하는지 확인
        if board[team1][i] <= graph[team1][i] and  board[team2][2-i] <= graph[team2][2-i]: 
            DFS(board,matchCnt+1,tc)
        board[team1][i] -= 1
        board[team2][2-i] -= 1

ans = [-1,-1,-1,-1]
for tc in range(4):
    graph=[]
    board=[[0 for i in range(3)] for j in range(6)]
    tmp = list(map(int, readl().split()))
    for cal in range(6):
        graph.append(tmp[3*cal:3*(cal+1)])
    for i in range(6):
        if sum(graph[i]) > 5 :
            break
    else:
        DFS(board, 0, tc)

for i in range(4):
    if ans[i] == -1:
        ans[i] = 0
print(*ans)