[알고리즘] 빙고 - 구현

문제 링크

빙고 : https://www.acmicpc.net/problem/2578

 

문제탐색

기본 원리 탐색

• 5x5 빙고를 구현하는 문제입니다.
  
  • 구체적으로는 시간의 흐름에따라 3개의 빙고가 나오는것을 캐치하는 문제입니다.
  • 빙고는 가로, 세로, 대각선 3종류가 가능하며 대각선은 5개를 모두 지우는 경우만 가능합니다.
• 그러므로 2차원배열을 사용하여 순차적으로 빙고를 진행하며 3개의 빙고가 나오는것을 계속 감지하는 코드를 짜야 합니다.

 

시간복잡도와 알고리즘

• 시간제한 : 1초
  • 약 1억번의 연산이 가능하다고 가정합니다.
• 빙고 크기 :  5x5
  
  • 빙고의 크기가 5x5로 고정되어있어 시간복잡도상 문제가 없을것으로 생각되지만 시간복잡도를 구해봅니다.

빙고게임의 과정을 크게 3가지로 나누면 아래와 같습니다.

1.  X표시 : 사회자가 부르는 수에 알맞는 수를 체크합니다. 모든 빙고판을 순회해야하므로 5X5의 연산이 필요합니다.
2. 빙고체크 : X표시 후 빙고가 몇개인지 체크합니다. 3개이면 종료합니다. 가로,세로,대각선 모든 빙고를 체크하면 총 12번의 연산이 필요합니다.
3. 반복 : 다음 사회자가 부르는 수에따라 위 1-2과정을 반복합니다. 최악의경우 총 25번의 연산이 필요합니다.

위에서 1번과 2번은 따로 수행되며 3번은 1-2번을 반복합니다. 연산횟수를 나타내면

반복횟수 * (X표시횟수 + 빙고체크 횟수) 와 같습니다.

최악의경우 25 * 37 = 927회 반복하므로 위 과정대로 수행해도 시간 복잡도상 문제가 없습니다.

 

=> 완전탐색을 통해 X표시 및 빙고체크 로직을 구현합니다.

 

코드설계하기

1. 빙고판을 2차원 리스트에 입력받습니다.
2. 사회자가 부를 수는 리스트에 입력받습니다.
3. 모두 0으로 초기화된 5x5 정답판 리스트를 생성합니다.
4. 아래 5-6 과정을 사회자가 부르는 수 리스트에 따라 순회합니다.
5. - X표시 : 빙고판을 순회하며 해당숫자를 찾고 같은위치 정답판에 1로 표기합니다.
6. - 빙고체크 : 정답판의 가로합, 세로합, 대각선합이 5가되면  count를 셉니다. 만약 3이면 몇번째 수 인지 출력합니다.

 

시도회차 수정사항

 

정답코드

import sys

bingo = []
host = []
count=0

paper = [[0 for x in range(5)]for x in range(5)] #빈 정답지 생성

for x in range(5):
    bingo.append(list(map(int,sys.stdin.readline().split()))) #정수로 변환후 빙고판에 입력

for x in range(5):
    for y in list(map(int,sys.stdin.readline().split())): #정수로 변환후 사회자에 단일 리스트로 입력
        host.append(y)


for target in host: #사회자가 말하게될 번호대로 반복합니다.
    countBingo=0
    for x in range(5):            # 빙고판을 순회하며 target값을 찾습니다. 
        for y in range(5):
            if bingo[x][y]==target:
                paper[x][y]=1

    #빙고 체크
    countBingo+=[sum(row) for row in paper].count(5) # 가로열 합중 5의 갯수를 찾아서 더합니다.
    countBingo+=[sum(row) for row in zip(*paper)].count(5) # zip을 활용하여 2차원리스트를 반전 시켜 세로열을 계산합니다.
    if sum(paper[i][i] for i in range(5))==5:#대각선 합을 구한후 5면 더합니다.
        countBingo+=1
    if sum(paper[i][5-1-i] for i in range(5))==5:#대각선 2
        countBingo+=1

    count+=1
    if countBingo>=3: #빙고가 3이상이면 정답 출력후 종료합니다.
        print(count) #몇번째 수인지 출력
        break