문제
코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.
이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다.
통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다.
선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.
입력
첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.
좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.
출력
첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.
예제 입출력
접근 및 코드
이 문제는 그래프 연결요소를 구하는 문제를 조금 응용했다고 볼수있다.
접근 방법은 다음과 같다.
1. 문제 판단
문제에서 입력으로 좌표가 주어지고, 음식물이 있는 좌표가 주어졌다.
즉, 이 문제는 격자(좌표평면)로 이루어진 격자형그래프라고 볼수 있다.
문제에서 음식물중 가장 큰것을 피해가고 싶다고 했고, 음식물은 상하좌우로만 연결될수 있다고 한다.
격자형 그래프에서 각 칸을 노드로 생각하면, 음식물이 연결된것은 그래프에서 연결요소를 구하는 것과 동일하다.
가장 큰 음식물의 크기를 구해야 하므로 그래프를 탐색하면서 연결요소를 구하고, 그중 가장 큰값을 반환해주면된다.
2. 그래프 만들기
그래프임을 판단했고 구하고자 하는 것을 알았다
주어진 정보로 그래프를 만들어 보겠다.
우선 주어진 가로 세로 길이로 2차원 배열을 만들어준다.
그리고 주어진 음식물의 좌표를 읽어서 2차원 배열에 표시해준다.
0,0부터 시작하도록 그래프를 만들었기 때문에, 주어진 음식물의 좌표는 넣을때 -1해서 넣어준다.
빈 공간은 0으로, 음식물은 1로 표현하도록 하겠다.
3. 그래프 탐색
그래프가 만들어졌으니 탐색을 하면된다.
구하고자 하는 것은 음식물이다.
따라서 반복문을 돌면서 음식물인 것(값이 1인것)을 찾아서 시작노드로 정하고, bfs탐색을 돌려준다.
노드를 탐색할떄 마다 +1해서 음식물인 칸이 몇인지 확인하고, 탐색한 칸은 0으로 바꿔서 다음 탐색때 안하도록 해준다.
탐색이 끝나면 카운트 하던 음식물의 크기가 나오게 되고, 지도상에 음식물이 없을 때까지 탐색을 하고, 나온 음식물 크기들을 비교해서 가장 큰 값을 출력해준다
코드는 다음과 같다.
import sys
from collections import deque
#n:세로길이, m: 가로길이, k: 음식물갯수
n,m,k = map(int,sys.stdin.readline().split())
#그래프 만들기 - 초기셋팅은 전부 0으로, 음식물을 입력받아서 채울것임
graph = [[0 for _ in range(m)] for _ in range(n)]
#음식물 위치 정보 입력 - 0을 안쓰고 1,1부터 사용하는 좌표가 입력으로 들어온다.
#0번부터 쓰고 싶기 떄문에 각 좌표에 -1을 해서 넣어준다.
for _ in range(k):
r,c = map(int,sys.stdin.readline().split())
#음식물을 1로 표시함
graph[r-1][c-1] = 1
#bfs함수 정의
def bfs(start_node:list) -> int:
dx = [0,0,-1,1]
dy = [-1,1,0,0]
need_visited = deque(list())
need_visited.append(start_node)
graph[start_node[0]][start_node[1]] = 0
count = 0
while need_visited:
current_x, current_y = need_visited.popleft()
count += 1
for i in range(4):
next_x = current_x + dx[i]
next_y = current_y + dy[i]
if next_x >= 0 and next_x < n and next_y >= 0 and next_y < m and graph[next_x][next_y] == 1:
#탐색한 것은 0으로 바꿔서 다음에 탐색안하도록 함.
graph[next_x][next_y] = 0
need_visited.append([next_x,next_y])
return count
#음식물의 최대사이즈
result_size = 0
#bfs탐색을 할때 시작노드를 정함 - 1인것만
for i in range(n):
for j in range(m):
#0일때는 탐색 x
if graph[i][j] == 1:
temp = bfs([i,j])
if result_size < temp:
result_size = temp
print(result_size)결과
