문제 설명
링크
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)
참고
'코딩테스트 > 백준' 카테고리의 다른 글
[백준] 7576번 토마토 파이썬 풀이 -dfs/bfs (0) | 2023.10.18 |
---|---|
[백준] 10026번 적록색약 파이썬 풀이 -DFS, BFS (1) | 2023.10.17 |
[백준] 14888번 연산자 끼워넣기 Python 파이썬 풀이 (0) | 2023.07.28 |
[백준] 2667번 단지번호 붙이기 Python 파이썬 풀이 (0) | 2023.07.27 |