[알고리즘] 백준 1743 파이썬 - 음식물 피하기

 

1743번: 음식물 피하기

 

문제

 

코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 

이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 

통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다. 

선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.

 

 

문제풀이

import sys
from collections import deque
n,m,k=map(int,input().split())
graph=[[0 for _ in range(m+1)] for _ in range(n+1)]
for _ in range(k):
    a,b=map(int,input().split())
    graph[a][b]=1
    
def bfs(x,y):
	#01
    ans=1
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    q=deque([(x,y)])
    graph[x][y]=2
    while q:
        x,y=q.popleft()
        #02
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<nx<=n and 0<ny<=m and graph[nx][ny]==1:
                q.append((nx,ny))
                graph[nx][ny]=2
                ans+=1
    return ans
#03
answer=0
for i in range(1,n+1):
    for j in range(1,m+1):
        if graph[i][j]==1:
            ans=bfs(i,j)
            answer=max(answer,ans)
print(answer)

- #01 : ans를 1로 설정해주고, dx와 dy는 각각 x와 y로 이동할 수 있는 좌표이다.

- #02 : nx와 ny는 x,y에서 이동한 후의 좌표값이다. 

          해당 좌표가 if문의 조건을 만족한다면, ans를 1 늘려주고, graph[nx][ny]=2로 바꿔준다.

- #03 : 최종적으로 bfs를 반복문을 돌려가며 최대값을 answer에 저장한다.

           참고로 bfs의 ans 값은 처음에 1로 초기화 되기에, 누적으로 값이 쌓이지 않는다.

           마지막으로 구한 최대 크기의 answer을 출력하면 된다.