[ BOJ ] 26598 : 색종이와 공예 ( GOLD 5 ) / Python

>> 문제 바로가기 (https://www.acmicpc.net/problem/26598)

문제

준성이는 색종이를 가위로 자르고 남은 색종이 조각들로 뭘 할지 생각해 보았다.

군 생활 동안 열심히 고민해 본 결과, 색종이를 다시 이어붙여 색종이 공예품을 만들기로 했다!

준성이가 색종이를 이어 붙일 때는 다음과 같은 규칙을 따른다.

1. 각 색종이 조각들은 변과 변을 맞대고 있으며, 일부 또는 전체가 겹치지 않는다.
2. 이어 붙어진 색종이 조각들은 2차원 상에서 세로 길이가 N, 가로 길이가 M인 빈틈없는 직사각형 모양이다.
3. 이때, 각 색종이 조각들이 모두 가로 길이와 세로 길이가 정수인 빈틈없는 직사각형 모양이라면 예쁜 색종이 공예품이라고 한다.

준성이는 열심히 만든 색종이 공예품을 당신에게 자랑하기 위해 보여줬다.

"ㅎㅎ 예쁘지?"

왠지 준성이가 기분이 좋아 보이는 것이 맘에 안 든다... 준성이가 만든 색종이 공예품을 보고 예쁘지 않다면 놀려주도록 하자!

입력

첫째 줄에 색종이 공예품의 세로 길이 N, 가로 길이 M이 공백을 두고 주어진다. (1 ≤ N, M ≤ 1 000)

다음 N개의 줄에 걸쳐 알파벳 대문자로 이루어진 길이가 M인 문자열이 주어진다.

상하좌우로 인접한 두 알파벳이 같다면 서로 같은 색종이 조각이고, 그렇지 않다면 서로 다른 색종이 조각이다.

알파벳 하나의 세로 길이와 가로 길이는 모두 1이며, 주어지는 숫자는 모두 정수다.

출력

입력으로 주어진 색종이 공예품이 예쁘다면 dd를 입력하고, 그렇지 않다면 BaboBabo를 출력한다.

풀이 과정

색종이 한 조각마다 BFS 를 수행한다.

색종이 조각이 직사각형인지 검토하기 위해, 색종이 조각을 BFS 했을 때 거쳐 간 칸의 개수가 색종이의 (최대 가로 인덱스 - 최소 가로 인덱스 + 1) x (최대 세로 인덱스 - 최소 세로 인덱스 + 1) 와 같다면 직사각형 색종이이다. 이 식이 맞지 않는 색종이 조각이 하나라도 있다면 BaboBabo 를 출력한다.

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)]

row = [-1, 1, 0, 0]
col = [0, 0, -1, 1]
def BFS(start_y, start_x):
    queue = deque()
    queue.append([start_y, start_x])
    focusing = maps[start_y][start_x]
    visited[start_y][start_x] = 1

    left = m
    right = -1
    up = n
    down = -1

    cnt = 1
    while queue:
        now = queue.popleft()
        left = min(left, now[1])
        right = max(right, now[1])
        up = min(up, now[0])
        down = max(down, now[0])

        for d in range(4):
            ny = now[0] + row[d]
            nx = now[1] + col[d]

            if 0 <= ny < n and 0 <= nx < m and visited[ny][nx] == 0 and maps[ny][nx] == focusing:
                cnt += 1
                visited[ny][nx] = 1
                queue.append([ny, nx])
    
    return [cnt, left, right, up, down]

result = True
for i in range(n):
    for j in range(m):
        if visited[i][j] == 0:
            result_cnt, left, right, up, down = BFS(i, j)

            if (right - left + 1) * (down - up + 1) != result_cnt:
                result = False
                break
    
    if result == False: break

print('BaboBabo' if result == False else 'dd')