[BOJ] 백준 1743번 음식물 피하기 (Python)

deannn.Park·2021년 8월 1일
0

BOJ - 백준

목록 보기
30/42
post-thumbnail

문제

코레스코 콘도미니엄 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를 풀어줬다.

profile
컴퓨터 관련 여러 분야 공부중

0개의 댓글