백준_BFS_음식물 피하기_1743_파이썬

✅문제

요약
0. 가로n 세로m 크기의 복도에 k개의 음식물 쓰레기가 떨어져있다
1. 음식물은 서로 인접하면(상하좌우) 커진다
2. 가장 큰 음식물의 크기를 구하라
ㅤ

✅입력

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

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

✅ 알고리즘 분류

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

💡풀이

흔한 BFS 풀이었다.
먼저 nxm 행렬을 돌면서 음식물이 떨어져 있는 곳이라면 큐를 만들고,
상하좌우 탐색을 하며 인접한 음식물의 개수를 구하고, 찾아본 음식물의 크기 중
가장 큰 것을 print하였다

from collections import deque

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

for _ in range(k):
    a, b = map(int, input().split())
    arr[a-1][b-1] = 1

direct = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visit = [[0]*m for _ in range(n)]
ans = 0

for r in range(n):
    for c in range(m):
        if arr[r][c] and not visit[r][c]:
            Q = deque([(r, c)])
            cnt = 0
            visit[r][c] = 1

            while Q:
                nr, nc = Q.popleft()
                cnt += 1
                for d in direct:
                    sr, sc = nr+d[0], nc+d[1]
                    if 0 <= sr < n and 0 <= sc < m and not visit[sr][sc] and arr[sr][sc]:
                        visit[sr][sc] = 1
                        Q.append((sr, sc))
            ans = max(ans, cnt)

print(ans)