[BOJ / 백준] 1743 음식물 피하기 python / 파이썬

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

1743번: 음식물 피하기

---

1) 요구사항 분석 : 문제 읽기

음식물 중 가장 큰 음식물의 크기를 출력

 

 

2) 설계 : 접근 방식

2차원 배열을 만들어서 음식물의 위치를 1로 표시해주고

dfs를 이용해서 풀었다.

 

가장 큰 음식물의 크기를 구하기 위해 max함수를 사용했다.

import sys
sys.setrecursionlimit(10**7)

n, m, k = map(int, input().split())
arr = [[0 for _ in range(m)] for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]
di = [0, -1, 0, 1]
dj = [-1, 0, 1, 0]

for _ in range(k):
    a, b = map(int, input().split())
    arr[a - 1][b - 1] = 1

def in_range(x, y):
    return 0 <= x < n and 0 <= y < m

def dfs(x, y):
    global tem
    visited[x][y] = True

    for a in range(4):
        ni = di[a] + x
        nj = dj[a] + y
        if in_range(ni, nj) and not visited[ni][nj] and arr[ni][nj] == 1:
            tem += 1
            dfs(ni, nj)

ans = 0

for i in range(n):
    for j in range(m):
        if visited[i][j] == False and arr[i][j] == 1:
            tem = 1
            dfs(i, j)
            ans = max(ans, tem)

print(ans)