[백준] 1743번 음식물 피하기(Avoid The Lakes ) 파이썬 Python

문제 설명

링크

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

문제

Farmer John's farm was flooded in the most recent storm, a fact only aggravated by the information that his cows are deathly afraid of water. His insurance agency will only repay him, however, an amount depending on the size of the largest "lake" on his farm.

The farm is represented as a rectangular grid with N (1 ≤ N ≤ 100) rows and M (1 ≤ M ≤ 100) columns. Each cell in the grid is either dry or submerged, and exactly K (1 ≤ K ≤ N×M) of the cells are submerged. As one would expect, a lake has a central cell to which other cells connect by sharing a long edge (not a corner). Any cell that shares a long edge with the central cell or shares a long edge with any connected cell becomes a connected cell and is part of the lake.

 

존의 농장에 홍수가 왔는데 농장은 2차원 배열 (N * M)으로 나뉘고 각 칸은 침수되거나 건조한 상태 중 하나이다.

침수된 칸은 K개로 입력이 주어짐.

보험비는 홍수로 인해 생긴 강의 크기에 따라 다른데, 이 강은 칸들이 간선으로 이어진 걸 말한다.

긴 강의 길이를 구하면 되는 문제 (= 침수된 칸이 가장 길게 이어진 개수)

 

입력

• Line 1: Three space-separated integers: N, M, and K 
• Lines 2..K+1: Line i+1 describes one submerged location with two space separated integers that are its row and column: R and C

출력

• Line 1: The number of cells that the largest lake contains.

예제입력/출력

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

4

 

문제 풀이

아이디어

n*m크기의 0으로 초기화한 2차원 배열을 만들고 침수한 곳은 1로 표기

dfs이용해 침수된 곳의 길이를 구한다. 

풀이

import sys
sys.setrecursionlimit(10**6) #재귀호출 제한을 늘림
input = sys.stdin.readline

n,m,k= map(int,input().split()) #n: row, m:column k: submerged

field= [[0]*m for _ in range(n)] #농장필드 전체 0으로 초기화

for i in range(k): #침수된 지역 1로 표시
  r,c= map(int,input().split())
  field[r-1][c-1]=1

dx=[0,0,-1,1] #위,아래,왼,오 확인을 위한 방향설정
dy=[-1,1,0,0]

lake_max_size=0 # 최종값
size=0 #강의 길이

def dfs(x,y):
  for i in range(4): #사방면을 둘러봄
    nx= x+dx[i]
    ny= y+dy[i]
    if(nx<0 or ny<0 or nx>= n or ny >= m): continue #농장 범위를 벗어난 경우
    if(field[nx][ny]==1): #침수된 지역일 경우
      global size
      size+=1 #사이즈 +1
      field[nx][ny]=2 #이미 체크한 지역임을 2로 표시함.
      dfs(nx,ny) #재귀호출로 다음 이어진 부분을 조사한다


for j in range(n):
  for u in range(m):
    if(field[j][u]==0): continue 
    if(field[j][u]==1): #침수된 지역의 경우 조사
      dfs(j,u)
      if(size>lake_max_size): lake_max_size=size
      size=0 #dfs를 돌린 후 size를 초기화 해주어야 함

print(lake_max_size)

참고