[백준 / python] 2578번 빙고

오늘은 구현 유형인 백준 2578번 문제, 빙고를 풀어보겠습니다!

 

< 문제 확인 >

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

---

📌 문제 탐색하기 

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

사회자가 부르는 숫자 순서에 따라 철수가 언제 "빙고"를 외치는지를 알아내는 것입니다.

구체적으로 몇 번째 숫자가 불렸을 때 빙고가 성립되는지를 찾아야 합니다.

 

1부터 25까지의 숫자를 한 줄에 5개씩 5줄에 걸쳐 빙고판을 입력합니다.

사회자가 부르는 숫자를 지워가면서 가로줄, 세로줄, 대각선이

모두 지워지면 해당하는 한 줄은 빙고가 완성된 것입니다!

 

총 3줄이 완성되는 순간 철수는 "빙고"라고 외치며 출력 결과로는

사회자가 지금까지 부른 숫자 개수 즉, 그동안 지워진 숫자의 개수를 출력해야 합니다.

---

그동안 풀었던 문제보다는 구현할 내용이 많은 것 같네요 ㅠㅠ

 

먼저, 빙고판을 2차원 리스트로 입력받고 각 숫자의 위치를 저장할 수 있는 딕셔너리를 만듭니다.

그리고 모든 빙고판의 위치를 False로 저장하고,

사회자가 숫자를 부르면 해당하는 위치를 True로 변경합니다!

 

이후 가로, 세로, 대각선 줄을 확인하며 한 줄이 빙고가 되는지 확인하고,

총 3줄 이상의 빙고가 만들어질 때 사회자가 부른 숫자의 횟수를 출력하면 됩니다.

 

✔️ 가능한 시간복잡도

빙고판의 크기는 고정되어 있고, 숫자의 범위도 제한적입니다.

각 숫자를 체크할 때마다 가로 5줄, 세로 5줄, 대각선 2줄 총 12줄을 검사해야 합니다.

사회자가 부를 수 있는 숫자의 최대값은 25이므로, O(12*25) = O(300) = O(1)로 나타낼 수 있습니다.

---

📌 코드 설계하기

- 문제 탐색하기 과정을 기반으로 이 문제를 해결하기 위한 로드맵을 그리는 과정
- 어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 빙고판을 저장하는 리스트와 사회자가 부르는 숫자를 저장할 리스트를 입력 받습니다.

2. 숫자 체크를 위한 리스트를 모두 False로 초기화합니다.

3. 사회자가 숫자를 부를 경우 해당 위치의 빙고판을 True로 변경합니다.

4. 가로, 세로, 대각선 총 12개의 줄이 모두 True인지 확인하는 함수를 구현합니다.

5. 한 줄 빙고가 3개 이상인지 확인 후 지금까지 부른 숫자의 개수를 출력합니다.

---

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

무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면,

내가 어떤 실수를 해서 해당 문제를 틀렸는지 모른다.

- 틀렸습니다를 받았다면 왜 틀렸는지, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

런타임 에러 발생! 그 이유는 call_numbers 리스트의 구조와

for 루프에서 접근하는 방식의 불일치에 있었습니다.

# call_numbers의 구조
[
    [5, 10, 7, 16, 2],
    [4, 22, 8, 17, 13],
    [3, 18, 1, 6, 25],
    [12, 19, 23, 14, 21],
    [11, 24, 9, 20, 15]
]

# 사회자가 부르는 숫자 입력 코드
# append로 작성한 부분을 extend로 수정해야함!
call_numbers = []
for _ in range(5):
    call_numbers.extend(list(map(int, input().split())))

---

📌 정답 코드

# 빙고 입력
bingo = []
for _ in range(5):
    bingo.append(list(map(int, input().split())))

# 사회자가 부르는 숫자 입력
call_numbers = []
for _ in range(5):
    call_numbers.extend(list(map(int, input().split())))

# 번호 체크 리스트, 해당 위치가 불린 경우 True로 표시!
check = [[False] * 5 for _ in range(5)]

# 숫자 위치 저장용 딕셔너리
number_position = {}
for i in range(5):
    for j in range(5):
        number_position[bingo[i][j]] = (i, j)

def count_bingo():
    count = 0
    # 가로줄 빙고 확인 (5줄)
    for i in range(5):
        if all(check[i]): count += 1
    
    # 세로줄 빙고 확인 (5줄)
    for j in range(5):
        if all(check[i][j] for i in range(5)): count += 1
    
    # \ 대각선 빙고 확인 (1줄)
    if all(check[i][i] for i in range(5)): count += 1
    
    # / 대각선 빙고 확인 (1줄)
    if all(check[i][5 - 1 - i] for i in range(5)): count += 1
    
    return count

# 숫자 불린 순서에 따라 체크
for index, number in enumerate(call_numbers):
    x, y = number_position[number]
    check[x][y] = True
    
    if count_bingo() >= 3:
        print(index + 1)
        break

지금까지 풀어봤던 구현 문제중 가장 어려웠지만 필요한 것들이 무엇인지 이해하면서

풀어보니 해결할 수 있었습니다!

 

 

코테 챌린지 3기 파이팅 :)

@why_dev_says_no