[코딩테스트][백준] 🔥 백준 6987번 "월드컵" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🛠️ 미해결

• 풀이시간 : 1시간 30분
• 문제 설명 : 각 경기에 대해서 각팀에 대해서 경기에 대한 점수를 기록하고 이것이 가능한지 여부를 따지는 문제이다.
• 틀린 이유 : 시간복잡도 계산 시 연산 횟수를 대략적으로 따진 후, 계산을 수행하는 방식을 사용하는데 이 때, 케이스 내에서 계산되는 연산횟수를 포함시키지 않는 습관이 있었다. 그래서 연산 수가 넘어가는데도 방법을 바꾸지 못하였다.

📖 상세 설명

1. 각 경기의 기록에 대해 받아서 세팅을 한다.
2. 해당 경기당 두팀에 대해서 이기고, 지고, 비기는 과정을 DFS를 통해 접근한다. 해당 재귀 수행마다 실제 결과에서 빼주어 결과를 확인한다.
3. 재귀의 끝, 즉 15경기가 수행된다면 해당 결과가 주어진 결과와 일치할 수 있는지 확인한다. 즉 결과값에서 빼주므로 전부 0이되는지를 확인한다.

🕒 Python 풀이시간: x

def check_possible(results, matches, idx):
    if idx == 15:
        for team_result in results:
            if team_result != [0, 0, 0]:
                return False
        return True

    t1, t2 = matches[idx]
    
    # t1 승리, t2 패배
    if results[t1][0] > 0 and results[t2][2] > 0:
        results[t1][0] -= 1
        results[t2][2] -= 1
        if check_possible(results, matches, idx + 1):
            return True
        results[t1][0] += 1
        results[t2][2] += 1

    # t1 무승부, t2 무승부
    if results[t1][1] > 0 and results[t2][1] > 0:
        results[t1][1] -= 1
        results[t2][1] -= 1
        if check_possible(results, matches, idx + 1):
            return True
        results[t1][1] += 1
        results[t2][1] += 1

    # t1 패배, t2 승리
    if results[t1][2] > 0 and results[t2][0] > 0:
        results[t1][2] -= 1
        results[t2][0] -= 1
        if check_possible(results, matches, idx + 1):
            return True
        results[t1][2] += 1
        results[t2][0] += 1

    return False

def solve():
    teams = 6
    matches = [(i, j) for i in range(teams) for j in range(i + 1, teams)]
    
    results = []
    for _ in range(4):
        input_data = list(map(int, input().split()))
        results.append([input_data[i:i+3] for i in range(0, 18, 3)])

    for result in results:
        if check_possible(result, matches, 0):
            print(1, end=" ")
        else:
            print(0, end=" ")

if __name__ == "__main__":
    solve()

이렇게 Python으로 백준의 "월드컵" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊