[ BOJ ] 16458 : 가장 큰 숫자 ( GOLD 5 ) / Python

문제

여러 개의 숫자들이 주어졌을 때, 이들 중 가장 큰 숫자를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 n, m(15 ≤ n ≤ m ≤ 1000)이 주어진다. 다음 n개의 줄에는 공백(' ')과 별 표('*')로 이루어진 숫자들이 주어진다. 각 줄마다 총 m개의 문자가 있다.

모든 숫자들은 어떤 자연수 k에 대해 가로 3k, 세로 5k 크기의 직사각형에 딱 맞게 들어가고, 이 직사각형을 다시 15개의 k × k 정사각형들로 분할할 경우 각 정사각형 안의 문자들은 모두 공백 혹은 별 표 중 한 종류로만 이루어져 있음이 보장된다.

위에서 언급한 숫자를 포함하는 직사각형들에 대해, 어떤 직사각형도 서로 겹쳐져 있지 않다. 또한 어떤 직사각형도 상하좌우 혹은 대각선 방향으로 맞닿아 있지 않다. 가장 큰 숫자는 하나만 주어진다.

출력

첫째 줄에 가장 큰 숫자를 출력한다.

풀이 과정

별 모양의 문자가 어떤 숫자인지 판단하는 과정에서 애를 좀 먹었다.

1. 숫자끼리는 겹치지 않으니 왼쪽 위부터 오른쪽 아래까지 차례대로 찾아가며 숫자의 왼쪽 시작점을 먼저 찾는다.

2. 시작점을 찾으면 연결된 별이 몇 개 있는지를 이용해 숫자를 판별한다.

만약 왼쪽 위 시작점에서 아래로 0칸, 오른쪽으로 1칸 별이 연결되어 있다면 1, 2

만약 왼쪽 위 시작점에서 아래로 4칸, 오른쪽으로 0칸 별이 연결되어 있다면 4, 6

만약 왼쪽 위 시작점에서 아래로 0칸, 오른쪽으로 2칸 별이 연결되어 있다면 3, 7

만약 왼쪽 위 시작점에서 아래로 4칸, 오른쪽으로 2칸 별이 연결되어 있다면 0, 8

 

만약 왼쪽 위 시작점에서 아래로 2칸, 오른쪽으로 2칸 별이 연결되어 있다면 5, 9

1x1 별 사각형이 아닌 2x2 사각형, 3x3 사각형으로 그려져 있어도 다음과 같은 관계는 비례 관계라서

아래로 8칸, 오른쪽으로 4칸 별이 연결되어 있다면 2x2 사각형로 이루어진 0, 8 ( 아래로 4칸, 오른쪽으로 2칸 ) 임을 확인할 수 있다.

 

다음과 같은 방법으로 숫자를 대략적으로 걸러주고, 사각형의 길이까지 알아내면

두 숫자 그림의 차이점을 임의로 잡아 숫자를 정확하게 판별한다.

 

이를 이용해 가장 크게 그려진 숫자를 찾는다.

 

숫자를 찾은 이후에는 BFS를 이용해 숫자가 그려진 영역에 나중에 접근하지 않도록 탐색하여 방문 처리를 진행했다.

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
maps = [list(input().rstrip()) for _ in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]

for i in range(n): 
    for j in range(m-len(maps[i])):
        maps[i].append(' ')

row = [-1, 1, 0, 0, -1, -1, 1, 1]
col = [0, 0, -1, 1, -1, 1, -1, 1]

max_number = 0
max_side = 0

for i in range(n):
    for j in range(m):
        if visited[i][j] == 0 and maps[i][j] == '*':
            down = 1
            queue = deque()
            queue.append((i, j))

            while queue:
                y, x = queue.popleft()
                if y + 1 < n and maps[y + 1][x] == '*':
                    queue.append((y + 1, x))
                    down += 1

            right = 1
            queue = deque()
            queue.append((i, j))
            
            while queue:
                y, x = queue.popleft()
                if x + 1 < m and maps[y][x + 1] == '*':
                    queue.append((y, x + 1))
                    right += 1
            
            now_number = 0
            side = 0
            if down * 2 == right: # 1, 2
                side = down
                if maps[i + (side)][j + (side * 2)] == '*':
                    now_number = 2
                else:
                    now_number = 1
            
            elif down == right * 5: # 4, 6
                side = right
                if j + side < m and maps[i + (side * 2)][j + (side)] == '*':
                    now_number = 6
                else:
                    now_number = 4

            elif down * 3 == right: # 3, 7
                side = down
                if maps[i + (side * 2)][j + (side * 2)] == '*':
                    now_number = 3
                else:
                    now_number = 7

            elif down * 3 == right * 5: # 0, 8
                side = down // 5
                if maps[i + (side * 2)][j + (side)] == '*':
                    now_number = 8
                else:
                    now_number = 0

            elif down == right: # 5, 9
                side = down // 3
                if maps[i + (side)][j + (side * 2)] == '*':
                    now_number = 9
                else:
                    now_number = 5
            
            if side > max_side:
                max_side = side
                max_number = now_number

            # LEAST
            queue = deque()
            queue.append((i, j))
            visited[i][j] = 1

            while queue:
                y, x = queue.popleft()
                for d in range(8):
                    ny = y + row[d]
                    nx = x + col[d]

                    if 0 <= ny < n and 0 <= nx < m and visited[ny][nx] == 0 and maps[ny][nx] == '*':
                        visited[ny][nx] = 1
                        queue.append((ny, nx))
            
print(max_number)