[백준 BOJ / Python] 1743번 음식물 피하기

문제

통로에 음식물 쓰레기가 떨어져 있을 때, 인접한 쓰레기들끼리 하나의 덩어리로 보고 그중 가장 큰 덩어리의 크기를 구하는 문제이다. 인접한 음식물 쓰레기는 상하좌우로 붙어있는 경우를 말한다.

풀이

• 이 문제는 인접한 영역을 탐색하는 그래프 탐색 문제이다.
• BFS나 DFS를 활용해 연결 여부를 탐색하며 덩어리의 크기를 계산하면 된다.
• 먼저 음식물 쓰레기의 영역을 입력받는다.
• 이때, 쓰레기가 없는 상태는 1, 쓰레기가 있는 상태는 0으로 표시한다.
  (visited를 사용하지 않고 쓰레기가 있는 곳의 방문 여부를 쉽게 체크할 수 있다.)
• 인접 칸을 탐색했을 때, 다음칸으로 이동 가능하면 쓰레기 영역 크기를 늘리고 방문 표시를 해준다.
• max를 사용해 가장 큰 쓰레기 크기를 갱신한다.

Python 코드

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

n, m, k = map(int, input().split())
arr = [[1] * m for _ in range(n)]
for _ in range(k):
    x, y = map(int, input().split())
    arr[x - 1][y - 1] = 0  # 쓰레기가 있는 위치를 0으로 표시

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

# BFS를 이용해 연결된 쓰레기 덩어리의 크기를 구함
def count_area(i, j):
    cnt = 1
    q = deque([(i, j)])
    arr[i][j] = 1  # 방문 표시

    while q:
        x, y = q.popleft()

        # 상하좌우 탐색
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = x + dx, y + dy

            if not in_range(nx, ny):  # 범위를 벗어나면 패스
                continue
            if arr[nx][ny]:  # 쓰레기가 없으면 패스
                continue

            cnt += 1 # 영역 크기 증가
            arr[nx][ny] = 1  # 방문 표시
            q.append((nx, ny))

    return cnt

# 최대 쓰레기 덩어리 크기 계산
max_ = 0
for i in range(n):
    for j in range(m):
        if not arr[i][j]:  # 쓰레기가 있는 경우
            max_ = max(count_area(i, j), max_)

print(max_)

 

문제출처

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