[코드트리_IL]_뿌요뿌요

https://www.codetree.ai/curriculums

코드 트리 사이트의 문제를 사용했습니다.

코드트리

 

n * n 크기의 격자에 1에서 100 사이의 숫자가 각 칸에 하나씩 주어집니다. 이때 상하좌우로 인접한 칸끼리 같은 숫자로 이루어져 있는 경우 하나의 블록으로 생각하며, 블록을 이루고 있는 칸의 수가 4개 이상인 경우 해당 블록은 터지게 됩니다.

초기 상태가 주어졌을 때 터지게 되는 블럭의 수와, 최대 블록의 크기를 구하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에는 격자의 크기를 나타내는 n이 주어집니다.

두 번째 줄부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자가 순서대로 공백을 사이에 두고 주어집니다.

• 1 ≤ n ≤ 100
• 1 ≤ 주어지는 숫자 ≤ 100

출력 형식

터지게 되는 블럭의 수와 최대 블록의 크기를 공백을 사이에 두고 출력합니다.

문제 해결

'터지게 되는' 블록의 수와, 최대 블럭의 개수(크기)를 출력하는 문제이다.

터지지 않더라도 최대 블록의 개수는 카운팅 해줘야 한다.

4개 이상으로 한 개의 숫자에 대해 터지게 되는 블록이 나타났을 경우 area_cnt(터진) 변수에 카운팅을 해주고

else(3 이하의 블록 개수)인 경우에도 max값에 최댓값을 담아준 후 출력해 주었다.

 

n = int(input())
dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * n for _ in range(n)]

def in_range(x, y):
    return 0 <= x < n and 0 <= y < n

def dfs(x, y, now):
    global cnt, max_value
    visited[x][y] = True
    cnt += 1
    now = graph[x][y]
    for i in range(4):
        nx, ny = dx[i] + x, dy[i] + y
        if in_range(nx, ny) and not visited[nx][ny] and graph[nx][ny] == now:
            dfs(nx, ny, now)
    if cnt >= 4:
        return True
    else:
        return False

max_value = -1
area_cnt = 0

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            cnt = 0
            if dfs(i, j, 0):
                max_value = max(max_value, cnt)
                area_cnt += 1
            else:
                max_value = max(max_value, cnt)
                
print(area_cnt, max_value)