문제
코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.
이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다.
통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다.
선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.
입력
첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.
좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.
출력
첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.
풀이 방법
음식물 쓰레기 위치를 나타내는 2차원 배열 하나, 해당 칸에 방문했는지 여부를 나타내는 2차원 배열 하나를 준비한다.
쓰레기가 있는 칸만을 대상으로 주변에 몇 개의 쓰레기가 있는지 조사해야 한다.
쓰레기 개수를 1로 초기화하고, 방문한 칸의 좌표를 큐에 넣어주고 방문 처리한다.
큐가 빌 때까지 반복문을 돌리면서 인접한 4방향의 칸에 쓰레기가 들어 있는지 검사한다. 이 때, 해당 칸이 좌표 범위를 넘어가지 않으면서 이미 방문한 칸이 아니어야 검사를 수행한다. 해당 칸에 쓰레기가 있다면 방문 처리하고, 쓰레기 개수를 1개 늘린다. 쓰레기가 있던 칸의 좌표를 큐에 추가해 준다.
반복문을 모두 마치면 최종적으로 쓰레기의 개수를 리턴한다.
함수를 호출할 때마다 이전에 도출한 쓰레기 개수와 비교해서 더 큰것을 저장해둔다. 최종적으로 쓰레기 개수로 저장된 것을 출력한다.
코드
from collections import deque
n, m, k = map(int, input().split())
graph = [[0]*m for _ in range(n)]
visited = [[0]*m for _ in range(n)]
for _ in range(k):
r, c = map(int, input().split())
graph[r-1][c-1] = 1
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def bfs(x, y):
v = 1
queue = deque([(x, y)])
visited[x][y] = 1
#print(queue)
while queue:
px, py = queue.popleft()
for dx, dy in direction:
nx = px+dx
ny = py+dy
if 0 <= nx < n and 0 <= ny < m:
if visited[nx][ny] == 0 and graph[nx][ny] == 1:
visited[nx][ny] = 1
v += 1
queue.append((nx, ny))
return v
result = 0
for i in range(n):
for j in range(m):
if graph[i][j] == 1:
result = max(result, bfs(i, j))
print(result)