[백준/Python] (S4) 오버워치 월드컵 - 13923

Baekjoon Online Judge의 13923번 오버워치 월드컵 문제의 Python 풀이입니다.

13923번: 오버워치 월드컵

💻코드

while True:
    try:
        # 입력받은 팀의 수
        num_teams = int(input())
    except:
        break

    # 관객석의 자리배치도, 중복된 행 체크를 위한 집합, 정렬된 올바른 행
    seating_arrangement, seen_rows, correct_row_order = [input() for _ in range(num_teams)], set(), ''
    wrong_row, wrong_col = -1, -1

    # 올바른 행의 순서를 찾기
    for row in range(3):
        sorted_row = ''.join(sorted(seating_arrangement[row]))
        if sorted_row in seen_rows:
            correct_row_order = sorted_row
        seen_rows.add(sorted_row)

    # 잘못된 티셔츠를 입은 관객의 위치를 찾기
    for row_index in range(num_teams):
        for col_index in range(num_teams):
            current_shirt = seating_arrangement[row_index][col_index]
            for previous_col_index in range(col_index):
                # 잘못된 티셔츠를 찾았다면
                if wrong_row == -1 and current_shirt == seating_arrangement[row_index][previous_col_index]:
                    wrong_row = row_index
                    for other_row_index in range(num_teams):
                        if other_row_index != row_index and seating_arrangement[other_row_index][col_index] == current_shirt:
                            wrong_col = col_index
                    if wrong_col == -1:
                        wrong_col = previous_col_index
            if current_shirt not in correct_row_order:
                wrong_row, wrong_col = row_index, col_index

    # 올바른 티셔츠를 찾아서 출력하기
    for correct_shirt in correct_row_order:
        if correct_shirt not in seating_arrangement[wrong_row]:
            print(wrong_row + 1, wrong_col + 1, correct_shirt)

🧠풀이

이 문제는 오버워치 월드컵 응원석에 관객들이 앉아 있는 방식이 Latin Square의 조건을 만족해야 한다는 점에서 Latin Square와 관련이 있다. Latin Square는 각 행과 각 열에 같은 요소가 중복되지 않는 배열을 말한다. 이 조건을 만족하지 못하는 요소, 즉 잘못된 티셔츠를 입은 관객을 찾는 것이 이 문제의 목표다.

문제를 풀기 위해, 먼저 각 행을 검사하여 올바른 행의 순서를 확인한다. 이후 각 행과 열을 순회하며 라틴 스퀘어의 조건을 위반하는 요소를 찾아낸다. 조건을 위반하는 요소를 찾은 경우, 해당 관객이 올바르게 입어야 할 티셔츠를 결정하기 위해 올바른 행의 순서와 비교하여 누락된 티셔츠를 찾아낸다.

라틴 방진 - 위키백과, 우리 모두의 백과사전

🤔느낀 점

Latin Square에 대해 알게되었다...