문제
코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.
이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다.
통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다.
선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.
입력
첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.
좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.
출력
첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.
예제
입력
3 4 5
3 2
2 2
3 1
2 3
1 1출력
4힌트
# . . .
. # # .
# # . .위와 같이 음식물이 떨어져있고 제일큰 음식물의 크기는 4가 된다. (인접한 것은 붙어서 크게 된다고 나와 있음. 대각선으로는 음식물 끼리 붙을수 없고 상하좌우로만 붙을수 있다.)
풀이
사실 문제만 읽고는 무슨말인지 이해가 잘 되지 않았다. 근데 입출력, 힌트를 보면 그냥 dfs 또는 bfs를 사용하여 2차 리스트에서 가장 큰 그래프? 섬?을 찾는 문제이다.
힌트를 봐보자
# . . .
. # # .
# # . .위와 같은 지도가 있다고 가정 할 때, #이 음식물 쓰레기이고 이 #끼리 붙어있는 것 중 가장 큰 것의 크기를 출력하면 된다. 위의 경우에는 4이다.
import sys
sys.setrecursionlimit(10**4) # recursion limit 제한 설정
# 하 좌 상 우
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
def dfs(x, y):
global ch_matrix, matrix
ch_matrix[x][y] = 1 # 현재 위치 체크
cnt = 1 # 현재 위치의 크기 1
for d in range(4): # 현재 위치 기준으로 하,좌,상,우 탐색
nx = x + dx[d] # 탐색할 좌표
ny = y + dy[d]
# 탐색할 좌표가 지도를 벗어나지 않고, 값이 #이고, 이미 탐색한 곳이 아니라면
if 0 <= nx < N and 0 <= ny < M and matrix[nx][ny] == '#' and ch_matrix[nx][ny] == 0:
ch_matrix[nx][ny] = 1 # 좌표 체크
cnt += dfs(nx, ny) # dfs 실행 후 값을 cnt에 추가
return cnt # 모두 탐색 후 합한 값을 리턴
# 입력 받음
N, M, K = map(int, input().split())
garbage = [tuple(map(int, input().split())) for _ in range(K)]
# 지도 생성
matrix = []
for _ in range(N):
matrix.append(['.' for _ in range(M)])
for x, y in garbage:
matrix[x-1][y-1] = '#'
largest = 0 # 가장 큰 음쓰 크기
# 탐색 확인용 지도 생성
ch_matrix = []
for _ in range(N):
ch_matrix.append([0 for _ in range(M)])
# 지도에서 음쓰 위치 탐색
for x in range(N):
for y in range(M):
# 음쓰 탐색한 경우
if matrix[x][y] == '#' and ch_matrix[x][y] == 0:
ch_matrix[x][y] = 1 # 음쓰 위치 체크
largest = max(largest, dfs(x, y)) # dfs 후 largest 값과 비교 후 저장.
print(largest) # 출력recursion 런타임 에러때문에 recursion limit를 풀어줬다.
