[백준] 1260번 - 음식물 피하기 (파이썬)

 

백준 1260번 음식물 피하기 문제

 

 

"💡 문제 해결 아이디어 "

 

해당 문제는 BFS를 통해 해결할 수 있었다.

 

음식물 피하기는 어떤 가장 큰 음식물 쓰레기의 사이즈를 구하는 문제이다.

 

음식물 쓰레기는 근처(상,하,좌,우)에 붙어있으면 더 큰 크기로 변하는데

 

가장 많이 붙어있는 음식물 쓰레기의 범위를 구하면 되는 문제이다.

 

 

힌트

이러한 힌트가 문제에 주어지는데 이처럼 그래프를 형성하여 BFS를 통해 가장 많이 연결되어있는 '#'의 count를 구해 답을 유추했다.

 

0,0 ~ n-1,m-1 범위를 이중 반복문으로 모두 방문하며 그래프의 값이 '#'이면 bfs를 통해 연결되어있는 음식물 쓰레기의 갯수를 구해 return한다.

 

여기서 return 받은 값들 중 가장 큰 값이 답이기 때문에 max라는 변수를 -1로 초기화 시켜 max변수와 return 값을 비교해 더 큰 값을 저장해나가도록 구현하였다.

 

최종적으로 얻어진 max를 출력하면 문제를 해결할 수 있다.

 

 

코드

from collections import deque

def bfs(x,y):
    queue = deque([(x,y)])
    cnt = 1
    graph[x][y] = '.'
    while queue:
        a,b = queue.popleft()
        for i in range(4):
            nx,ny = a+dx[i],b+dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == '.':
                continue
            if graph[nx][ny] == '#':
                cnt+=1
                queue.append((nx,ny))
                graph[nx][ny] = '.'
    return cnt


dx = [-1,1,0,0]
dy = [0,0,-1,1]

max = -1
n,m,k = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(['.' for _ in range(m)])

for i in range(k):
    r,c = map(int,input().split())
    graph[r-1][c-1] = '#'

for i in range(n):
    for j in range(m):
        if graph[i][j] == '#':
            v = bfs(i,j)
            if v > max:
                max = v

print(max)