[백준 17025 🥇] Icy Perimeter

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

17025번: Icy Perimeter

문제풀이

import sys
from collections import deque

n=int(sys.stdin.readline())
icecream=[list(sys.stdin.readline().strip()) for _ in range(n)]
visited=[[0]*(n) for _ in range(n)]

def find_area_and_length():
    global visited, queue, icecream
    directions=[(0,1),(1,0),(0,-1),(-1,0)]
    area=0
    length=0
    while queue:
        y,x=queue.popleft()
        # 면적 구하기
        area += 1
        # 길이 구하기 -> 상하좌우로 범위를 벗어나거나, '.'이 존재하는 경우 length+=1
        for di in directions:
            dy=y+di[0]
            dx=x+di[1]
            if 0<=dy<n and 0<=dx<n:
                if icecream[dy][dx]=='.':
                    length+=1
            else:
                length+=1
        for di in directions:
            dy=y+di[0]
            dx=x+di[1]
            if 0<=dy<n and 0<=dx<n and visited[dy][dx]==0 and icecream[dy][dx]=='#':
                queue.append((dy,dx))
                visited[dy][dx]=1
    return area, length

max_area=0
min_length=0
for i in range(n):
    for j in range(n):
        if icecream[i][j]=='#' and visited[i][j]==0:
            queue=deque()
            queue.append((i,j))
            visited[i][j]=1
            area, length=find_area_and_length()
            if area>max_area:
                max_area=area
                min_length=length
            elif area==max_area:
                min_length=min(length, min_length)

print(max_area, min_length)

BFS를 이용하면 쉽게 풀 수 있는 문제였다

icecream 배열에 저장해둔 아이스크림 정보를 탐색하면서 icecream[i][j] 값이 '#'이면서 아직 방문하지 않은 요소인 경우

큐에 해당 인덱스를 넣어주고, 방문처리 해준 뒤에 BFS를 이용해서 해당 아이스크림 BLOB의 면적과 길이를 구한다. 

구한 면적이 최대 면적인 max_area보다 클 경우 max_area와 min_length를 갱신해준다.

max_area와 동일한 경우엔 min_length에 저장된 값과 비교하여 더 작은 값을 저장해준다. 

 

BFS를 이용해서 해당 블롭의 면적을 구하는 과정에 큐에서 아이스크립 블롭에 해당하는 인덱스를 pop해줄 때마다 상하좌우 탐색을 하면서

값이 '.'이거나 범위를 벗어나는 경우 해당 셀의 둘레로 판단해서 length+=1을 해줬다.