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

1743번: 음식물 피하기

분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

문제

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

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

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

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

입력

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

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.

출력

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

풀이

• 음식물이 떨어진 좌표를 표시했을 때 연결된 구역의 가장 큰 넓이를 구하는 문제이다.
• bfs를 사용하는 전형적인 문제로 음식물이 떨어져 있고 미방문한 곳만 찾아서 구역마다 넓이를 구하고 최대값을 갱신한다.

코드

from collections import deque

n,m,k = map(int, input().split())
arr = [[0]*m for _ in range(n)]
visit = [[0]*m for _ in range(n)]

directy = [0,0,1,-1]
directx = [1,-1,0,0]

for _ in range(k):
    r,c = map(int, input().split())
    # 좌표가 1부터 시작하므로 -1한 좌표에 저장
    arr[r-1][c-1]=1

mx = 0

# bfs할 때 해당 구역의 개수 세기
def bfs(i,j):
    visit[i][j]=1
    q = deque()
    q.append((i,j))
    cnt=1
    while q:
        y,x = q.popleft()
        for t in range(4):
            dy = directy[t]+y
            dx = directx[t]+x
            if 0<=dy<n and 0<=dx<m and arr[dy][dx]==1 and visit[dy][dx]==0:
                visit[dy][dx]=1
                cnt+=1
                q.append((dy,dx))
    return cnt

# 음식물이 있고 미방문한 곳만 bfs실행하고 최대값 업데이트하기
for i in range(n):
    for j in range(m):
        if arr[i][j]==1 and visit[i][j]==0:
            mx = max(bfs(i,j), mx)

print(mx)