[python/백준] 2578. 빙고(S4)

📌 문제 탐색하기

👉 문제바로가기

빙고판을 구성할 숫자를 입력받은 후 빙고가 될 수 있는 숫자5개쌍으로 이루어진 리스트(N)를 정의합니다.

사회자가 부른 리스트를 저장하고 해당 리스트 숫자를 하나씩 꺼내서 리스트N의 원소와 일치하는 경우 해당 원소를 0으로 변경합니다.

한 줄이 소거될 수 있는 경우는 가로(5가지), 세로(5가지), 대각선(2가지)입니다.

한 줄이 모두 0인 라인이 3개가 되면 빙고가 되는 문제입니다.

사회자가 부른 숫자를 저장하는 리스트에 대해 무작위로 숫자 5개를 골라서 리스트 N의 조합과 일치하는지 판단하려고 했으나, 해당 리스트의 숫자는 알 필요가 없고 일치여부만 구하면 되기 때문에 사회자가 부르는 숫자와 동일한 빙고판 자리의 원소에 대해 0으로 변경하는 방법을 선택했습니다.

알고리즘 선택

빙고판의 숫자를 모두 탐색하면서 사회자가 부른 숫자와 일치하는지 판단해야하기 때문에 브루트포스 알고리즘으로 접근합니다.

가능한 시간복잡도

빙고판 배열에 있는 숫자는 5*5=25개이고 사회자가 부르는 숫자도 25개입니다. 따라서 최대 약25x25=625번의 연산이 수행됩니다.

📌 코드 설계하기

1. 사용자로부터 빙고판의 숫자 배열(N)과 사회자가 부르는 수(speak)에 대해 각각 Input을 받습니다.
2. 빙고판을 차례대로 돌면서 사회자가 부르는 수와 일치하는지 판단합니다.
3. 일치하는 경우 해당 빙고판 자리의 숫자를 0으로 변경합니다.
4. 빙고가 3개가 되기 위해서 최소한 사회자가 12개 이상의 원소를 불러야 하기 때문에, 사회자가 부른 값이 12개 이상이 될 경우 5개의 요소가 전부 삭제된 줄의 갯수를 판단하는 함수를 실행합니다.
5. 가로, 세로, 대각선 각각의 경우에 대해 반복문을 돌며 0이 5개인 줄이 3개이상 생기면 함수를 종료합니다.
6. 사회자가 부른 값을 저장한 리스트에서 몇 번째 요소까지 왔는지를 나타내는 변수에 1을 더해서 출력합니다.
   사회자가 부른 값이 몇번째인지 구하려면 빙고가 될 때(모두 0인 라인이 3줄 이상일때)의 speak리스트에서 마지막으로 불러온 원소의 인덱스에 1을 더해야 합니다.

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

1회차

check함수에서 가로, 세로, 대각선1, 대각선2의 반복문을 돌릴때, 가로에서 0의 갯수가 5개인 줄을 찾지 못했을 경우 세로와 관련된 반복문을 돌리기 전에 시도횟수를 초기화해주어야합니다.

📌 정답 코드

import sys

#시도횟수 체크 함수
def check(arr):
  line = 0
  #가로
  for i in range(5):
    if arr[i][0] == 0:
      temp = 0  # 시도횟수
      for j in range(5):
        if arr[i][j] == 0:
          temp += 1
      if temp == 5:
        line += 1  #모두 0인 줄의 갯수

  #세로
  for i in range(5):
    if arr[0][i] == 0:
      temp = 0  # 시도횟수
      for j in range(5):
        if arr[j][i] == 0:
          temp += 1
      if temp == 5:
        line += 1

  #대각선1
  temp = 0  # 시도횟수
  for i in range(5):
    if arr[i][i] == 0:
      temp += 1
  if temp == 5:
    line += 1

  #대각선2
  temp = 0  # 시도횟수
  for i in range(5):
    if arr[i][4 - i] == 0:
      temp += 1
  if temp == 5:
    line += 1

  if line >= 3:
    return True
  else:
    return


# 빙고판 생성
N = [list(map(int, sys.stdin.readline().split())) for _ in range(5)]

speak = []  #사회자가 부른 숫자 리스트

count = 0

for _ in range(5):
  speak += map(int, input().split())

for i in range(25):
  for j in range(5):
    for k in range(5):
      if N[j][k] == speak[i]:
        N[j][k] = 0
        count += 1
        break
  if count >= 12:
    result = check(N)
    if result:  #빙고 3회
      print(i + 1)
      break