[백준] 1743번 음식물 피하기(DFS 알고리즘)(Python - 파이썬)

백준 1743번 문제입니다. (solved.ac)기준 실버 1 문제입니다.

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

1743번: 음식물 피하기

아래 문제들과 유사한 문제입니다.

 

[알고리즘 문제풀이] - [백준] 1012번 유기농 배추(DFS 알고리즘)(Python)

[백준] 1012번 유기농 배추(DFS 알고리즘)(Python)

[알고리즘 문제풀이] - [백준] 2667번 단지번호붙이기(DFS알고리즘)(Python)

[백준] 2667번 단지번호붙이기(DFS알고리즘)(Python)

 

예제 입력  1 :

3 4 5
3 2
2 2
3 1
2 3
1 1

예제 출력 1 :

4

쓰레기가 있는 곳의 좌표를 입력받을 때 접근에 용이하도록 graph를 [n+1][m+1] 의 크기로 선언해 주었고 쓰레기의 정보를 입력받으면

[
[0, 0, 0, 0, 0], 
[0, 1, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 1, 1, 0, 0]
]

위와 같은 형태로 그래프가 생성됩니다. 0은 쓰레기가 없는 곳, 1은 쓰레기가 있는 곳입니다. (0,0)부터 탐색을 시작하여 쓰레기가 발견되면 그 인접한(상, 하, 좌, 우)도 탐색하여 인접한 곳에도 쓰레기가 존재한다면 쓰레기의 크기를 증가시키고 방문처리(1->0)를 하여 이미 탐색된 곳이 중복 탐색되지 않도록 하였습니다.

import sys
# 재귀함수 최대 호출 횟수 증가
sys.setrecursionlimit(10**7)
# N은 세로길이, M은 가로길이, K는 음식물 쓰레기의 개수
n, m, k = map(int, sys.stdin.readline().rstrip().split())

# size를 전역변수로 선언
global size
size = 0
ans = 0

# 편하게 접근하기 위해 행,열에 빈칸을 하나씩 더 넣어둠
# 0이 빈곳이고 1을 쓰레기가 있는 곳으로 설정
# 처음에는 graph를 모두 0으로 초기화
graph =[[0] * (m+1) for _ in range(n+1)]

# 쓰레기가 있는 곳의 좌표를 입력 받아 그래프에 쓰레기(1)를 삽입
for _ in range(k) :
    x, y = map(int, sys.stdin.readline().rstrip().split())
    graph[x][y] = (1)

# 예제 입력 1 기준
# [[0, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 1, 0], [0, 1, 1, 0, 0]]

# 깊이 우선 탐색을 위한 Dfs함수 선언
def Dfs(x, y):

    global size

    # 범위를 넘으면 탐색 종료
    if x < 0 or x > n or y < 0 or y > m:
        return False
    # 쓰레기(1)가 있다면
    if graph[x][y] == 1 :
        # 쓰레기의 크기 1 증가
        size += 1
        # 방문 처리
        graph[x][y] = 0
        # 인접한곳(상하좌우) 탐색
        Dfs(x+1, y)
        Dfs(x-1, y)
        Dfs(x, y+1)
        Dfs(x, y-1)

        return True

    return False



for i in range(n+1) :
    for j in range(m+1) :
        if Dfs(i,j) == True :
            # ans(현재까지 중 최대 쓰레기의 크기, 정답)에 쓰레기의 크기(size)와
            # ans(현재까지 중 최대 쓰레기의 크기, 정답)을 비교하여
            # 더 큰값을 ans(현재까지 중 최대 쓰레기의 크기, 정답)에 넣어줌
            ans = max(size, ans)
            # 쓰레기의 크기를 0으로 초기화
            size = 0

print(ans)