[백준] 1743 음식물 피하기(DFS) - Python

https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

 

- 문제 설명

복도에 떨어진 음식물 중 가장 크기가 큰 음식물의 크기를 구하는 문제이다.

2차원 배열 속에서 음식물이 서로 붙어있는 경우 한덩이의 음식물로 보고 크기를 구한다.

 

첫째 줄에 복도의 세로길이 N, 가로길이 M, 음식물 쓰레기 개수 K 를 입력받는다.

이후 K개의 줄에 음식물의 위치를 입력받는다.

 

- 입출력 예시

DFS와 BFS방식 둘다 풀이가 가능하지만 DFS를 공부중이라 DFS방식으로 풀었다.

 

코드

# 1743 음식물 피하기
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**4)    # recursion 런타임 에러때문에 recursion limit를 풀어줌

def dfs(a, b):
    global visit
    visit[a][b] = 1     # 현재위치 방문체크
    size = 1            # 음식물이 있으므로 size = 1
    for r, c in delt:
        # 4방향 델타탐색을 하며 복도 범위안이고, 음식물이 있으며 방문한적 없는 곳이 있다면
        if 0 <= a+r < N and 0 <= b+c < M and corr[a+r][b+c] == '#' and visit[a+r][b+c] == 0:
            visit[a+r][b+c] = 1     # 방문체크
            size += dfs(a+r, b+c)   # 해당 위치에서 다시 DFS탐색하여 음식물 크기 산출
    return size        # 최종 음식물 크기 리턴

N, M, K = map(int, input().split())     # 복도크기, 음식물 위치 입력
corr = [['.']*M for _ in range(N)]      # 복도 생성
visit = [[0]*M for _ in range(N)]       # 방문한 곳인지 비교할 리스트

delt = [(-1, 0), (1, 0), (0, -1), (0, 1)]   # 탐색을 위한 델타배열
size_max = 0
# 음식물 생성
for i in range(K):      
    y, x = map(int, input().split())
    corr[y-1][x-1] = '#'
# 복도를 순회
for r in range(N):
    for c in range(M):
        # 현재 위치에 음식물이 있고 방문한 적이 없다면
        if corr[r][c] == '#' and visit[r][c] == 0:
            # dfs탐색을 통해 가장 큰 음식물 크기 구하기
            size_max = max(size_max, dfs(r, c))

print(size_max)