[백준] 2578번(python 파이썬) - 빙고

문제 링크: https://www.acmicpc.net/problem/2578

2578번: 빙고

시간 제한	메모리 제한	제출	정답	맞힌사람	정답비율
1 초	128 MB	13643	6251	5175	45.817%

문제

빙고 게임은 다음과 같은 방식으로 이루어진다.

먼저 아래와 같이 25개의 칸으로 이루어진 빙고판에 1부터 25까지 자연수를 한 칸에 하나씩 쓴다

다음은 사회자가 부르는 수를 차례로 지워나간다. 예를 들어 5, 10, 7이 불렸다면 이 세 수를 지운 뒤 빙고판의 모습은 다음과 같다.

 

차례로 수를 지워가다가 같은 가로줄, 세로줄 또는 대각선 위에 있는 5개의 모든 수가 지워지는 경우 그 줄에 선을 긋는다.

이러한 선이 세 개 이상 그어지는 순간 "빙고"라고 외치는데, 가장 먼저 외치는 사람이 게임의 승자가 된다.

철수는 친구들과 빙고 게임을 하고 있다. 철수가 빙고판에 쓴 수들과 사회자가 부르는 수의 순서가 주어질 때, 사회자가 몇 번째 수를 부른 후 철수가 "빙고"를 외치게 되는지를 출력하는 프로그램을 작성하시오.

입력

첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 빙고판에 쓰여진 수와 사회자가 부르는 수는 각각 1부터 25까지의 수가 한 번씩 사용된다.

출력

첫째 줄에 사회자가 몇 번째 수를 부른 후 철수가 "빙고"를 외치게 되는지 출력한다.

 

풀이

---

 이 문제는 풀이과정이 간단하다. 

입력된 수들이 3줄을 이루게 되었을 때 몇개의 수가 입력이 되었는지 출력하면 된다.

 

시간 복잡도를 줄이기 위해 사용한 방법은 다음과 같다.

 

• 딕셔너리의 key값에 빙고의 숫자값을 넣어주고 value값에 해당 좌표를 넣어준다.
  -> 숫자를 검색할때 시간복잡도를 줄여준다.
• 가로 빙고를 찾을때 set을 이용해서 해당 줄의 길이가 1일때 -> 빙고 ( 맞춘 숫자는 visited에 1로 표시됌)
• 빙고를 위한 최소 숫자입력 개수가 13개이상이므로 입력개수가 13일때 부터 bingo함수를 작동시킨다.

 

구현코드

---

arr = []
dic = {}
order = []
num = 0
visited = [[0]*5 for _ in range(5)]
for k in range(5):
    arr.append(list(map(int, input().split())))
    for i in range(5):
        dic[arr[k][i]] = [k, i]
for _ in range(5):
    order.append(list(map(int, input().split())))

def bingo(x, y):
    result = 0
    for i in range(5): # 가로빙고
        if visited[i][0] == 1:
            if len(set(visited[i])) == 1:
                result += 1

    for j in range(5): # 세로빙고
        temp = 0
        for i in range(5):
            if visited[i][j] == 1:
                temp += 1
            if temp == 5:
                result += 1

    temp = 0
    for i in range(5):
        if visited[i][i] == 1:
            temp += 1
        if temp == 5:
            result += 1

    temp = 0
    for i in range(5):
        if visited[i][4-i] == 1:
            temp += 1
        if temp == 5:
            result += 1

    if result >= 3:
        return True
    else:
        return False

for i in range(5): # 빙고가 되기 위한 최소 횟수가 13
    for j in range(5):
        if num >= 13:
            if bingo(i, j):
                print(num)
                exit()
        num += 1
        x = dic[order[i][j]][0]
        y = dic[order[i][j]][1]
        visited[x][y] = 1