[백준 1743] 음식물 피하기

문제

통로에 음식물들이 떨어져있고 근접한 음식물들이 모이면 큰 음식물 쓰레기가 된다.

음식물들이 떨어진 위치의 좌표가 주어질 때 가장 큰 음식물 쓰레기의 크기를 구하라.

어떤 음식물의 상하좌우에 음식물이 있을 때 근접한 음식물이라고 할 수 있다.

 

입력

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다.  그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다.

 

출력

첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.

---

접근

뭉쳐있는 음식물끼리 같은 번호를 매기고 넘버링한 숫자의 개수를 카운트하여 가장 큰 수를 찾는다.

 

구현

- 음식물이 1로 표현된 2차원 리스트에서 1을 찾았을 때 2부터 넘버링한다.

- 현재 좌표를 기준으로 상하좌우에 1이 있을 때 같은 번호를 매기도록 한다.

def dfs(y, x, number):
    matrix[y][x] = number

    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if check_range(ny, nx) and matrix[ny][nx] == 1:
            dfs(ny, nx, number)
            
for y in range(N):
    for x in range(M):
        if matrix[y][x] == 1:
            dfs(y, x, number)
            number += 1

- matrix에서 숫자 2부터 몇 개 있는지 카운트하고

- 최댓값을 찾는다.

for n in range(2, number):
    count = 0
    for y in range(N):
        for x in range(M):
            if matrix[y][x] == n:
                count += 1
    answer = max(answer, count)

---

전체 코드

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def check_range(y, x):
    return (0 <= y < N) and (0 <= x < M)

def dfs(y, x, number):
    matrix[y][x] = number

    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if check_range(ny, nx) and matrix[ny][nx] == 1:
            dfs(ny, nx, number)

N, M, K = map(int, input().split())
matrix = [[0 for _ in range(M)] for _ in range(N)]

for _ in range(K):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    matrix[y][x] = 1



answer = 0
number = 2
for y in range(N):
    for x in range(M):
        if matrix[y][x] == 1:
            dfs(y, x, number)
            number += 1


for n in range(2, number):
    count = 0
    for y in range(N):
        for x in range(M):
            if matrix[y][x] == n:
                count += 1
    answer = max(answer, count)
print(answer)