2578) 빙고

📌 문제 탐색하기

• 5 * 5 크기의 빙고판 입력
• 그 후 사회자가 불러주는 숫자가 5 * 5 배열로 입력
• 사회자가 숫자를 부른 후, 빙고판에서 빙고가 몇개 완성되었는지 확인
• 완성된 빙고가 3개 이상이라면 부른 숫자가 몇번째 숫자인지 출력

가능한 시간복잡도

시간 제한 : 1초
사회자는 총 25개의 숫자를 부르고, 빙고판에서 어느 위치에 숫자가 존재하는지 확인하는데도 총 25개의 비교연산이 필요하므로, 25 * 25 = 약 625개의 연산 필요

알고리즘 선택

시뮬레이션, 구현

📌 풀이하기

1. 사회자가 부른 숫자를 빙고판에 체크하기

   • 5 * 5 2차원 빙고판을 만들어두고, False 또는 0으로 마킹
   • 빙고판을 모두 탐색하며 사회자가 부른 숫자와 일치하면 True 또는 1로 마킹

   사회자는 총 25개의 숫자를 부르고, 빙고판에서 어느 위치에 숫자가 존재하는지 확인하는데도 총 25개의 비교연산이 필요하므로, 25 * 25 = 약 625개의 연산 필요 => 1초 안에 가능

2. 현재까지 완성된 빙고의 개수 확인하기
   빙고는 총 가로 5개, 세로 5개, 대각선 2개 존재

   1. 가로 빙고
   - 가로 빙고는 i번째 행에 대해 [i][0], [i][1], ..., [i][4]가 모두 마킹된(True)인지 확인
   - 5개 행에 대해 모두 확인 필요
   2. 세로 빙고
   - 세로 빙고는 i번째 행에 대해 [0][i], [1][i], ...,[4][i]가 모두 True인지 확인
   - 5개 열에 대해 모두 확인 필요
   3. 대각선 빙고
   - 대각선의 경우 /모양과 \모양이 있다. \모양은 [i][i], /모양은 [i][4-i]

   사회자가 숫자를 부른 후, 현재까지 완성된 빙고의 개수를 확인하는데 걸리는 연산 개수
   빙고는 총 가로 5개, 세로 5개, 대각선 2개가 존재하고 빙고 1줄당 총 5개의 비교연산이 필요하므로, 총 12 5 = 60번의 비교연산이 필요
   사회자가 최대 25개의 숫자를 부를 수 있으므로, 최악의 경우 25 60 == 1500개의 연산 필요 => 1초 안에 가능

📌 코드 설계하기

1. 문제의 input을 받는다.
2. 빙고판을 초기화한다.
3. 빙고의 개수를 구할 수 있는 함수를 구현한다. (행, 열, 대각선)
4. 사회자가 부르는 각 수에 대해 빙고판을 True로 체크하고 만족하는 빙고의 수를 확인한다.
5. 완성된 빙고의 수가 3개 이상인지 확인하고, 정답을 출력한다.

📌 시도 회차 수정 사항 (Optional)

📌 정답 코드

import sys

# 백준 2578

# 1. 빙고판 입력 받기
arr = []
for _ in range(5):
    arr.append(sys.stdin.readline().split())


# 2. 사회자가 부르는 수 list 담기
num = []
for _ in range(5):
    list = sys.stdin.readline().split()

    for i in list:
        num.append(i)

# 3. 빙고판 초기화
check_board = [[False for _ in range(5)] for _ in range(5)]

# 4. 빙고 수를 체크할 수 있는 함수
def check_row_bingo():
    count = 0
    for i in range(5):
        is_bingo = True
        for j in range(5):
            if not check_board[i][j]:
                is_bingo = False
                break
        if is_bingo:
            count += 1
    return count

# 5. 빙고 column 수를 확인하기 위한 함수 구현
def check_column_bingo():
    count = 0
    for j in range(5):
        is_bingo = True
        for i in range(5):
            if not check_board[i][j]:
                is_bingo = False
                break
        if is_bingo:
            count += 1
    return count

# 6. 대각선 빙고 수 확인하기 위한 함수 구현
def check_diagonal_bingo():
    count = 0
    # \ 모양 대각선
    is_bingo = True
    for i in range(5):
        if not check_board[i][i]:
            is_bingo = False
            break
    if is_bingo:
        count += 1
    
    # / 모양 대각선
    is_bingo = True
    for i in range(5):
        if not check_board[i][4 - i]:
            is_bingo = False
            break
    if is_bingo:
        count += 1

    return count


# 7. 사회자가 부르는 각 수에 대해 빙고판을 True로 체크하고,
#    만족하는 빙고의 수를 확인
for i in range(25):
    now_num = num[i]
    # 사회자가 부른 숫자의 빙고판 위치 확인하고 True로 표기
    for x in range(5):
        for y in range(5):
            if arr[x][y] == now_num:
                check_board[x][y] = True
    # 빙고판 True로 체크한 이후 빙고 몇개 완성됐는지 확인
    count = check_row_bingo() + check_column_bingo() + check_diagonal_bingo()
    # 완성된 빙고의 개수가 3개 이상이라면 해당 순서 출력
    if count >= 3:
        print(i + 1)
        break