백준 - 유기농 배추 (1012)

위 그림에서 1은 배추, 0은 흙이라고 생각하면 됨

여기서 배추흰지렁이는 1에 있음. 

 

상하좌우로 1(배추)가 있으면 지렁이 한마리만 있으면 됨.

위 그림에서는 빨간색 그림을 그린 것 처럼 지렁이가 배추들을 보호해줄 수 있음

그래서 최소 5마리의 지렁이가 필요함.

 

구현 코드

## 백준 특성상 메모장에서 데이터 가져오는 것 처럼 만듬
import sys
data_list = sys.stdin.readlines()

## 재귀 최대 횟수 늘리기 (Recursive Error 발생해서 추가해줌)
sys.setrecursionlimit(100000)

## dfs 함수 만들어줌
def dfs(matrix, x,y):
    if x < 0 or x >= len(matrix) or \ # x좌표가 0보다 작은 경우 혹은 행을 넘어가는 경우
       y < 0 or y >= len(matrix[0]) or \ # 위와 동일하게 y좌표
       matrix[x][y] != 1: # 해당 위치에 배추가 없는 경우
        return #빈 값을 반환해준다.
	
    # 위에 if문을 제외한 경우에는 0으로 바꿔주어
    # 경로를 방문했다는 표시를 해준다.
    matrix[x][y] = 0
    # 지렁이가 상하좌우로 배추를 커버할 수 있으니 4방향에 대해서도 dfs해준다
    dfs(matrix, x+1, y) # 아래
    dfs(matrix, x-1, y) # 위
    dfs(matrix, x, y+1) # 우측
    dfs(matrix, x, y-1) # 좌측 

## 여러 case가 올 수 있기에 case에 따른 index를 저장하기 위함
case_index = []

## case index를 찾아서 case_index리스트에 넣어줌
for index,value in enumerate(data_list):
	# 이부분은 data가 (x y 배추수)로 들어오면 case시작이기에 split써서 case시작을 구분해줌
    if len(value.split()) == 3: 
        case_index.append(index)

## 위에서 구한 case index를 하나씩 가져와서 수행함
for index in case_index:
    case = list(map(int,data_list[index].split())) # map함수를 써서 내부를 int로 변환
    matrix = [[0]*case[1] for _ in range(case[0])] # 가져온 배추밭을 matrix로 만들어줌
    

    # 배추가 있는 곳은 1이기에 1로 변환해줌
    for data in data_list[index+1: index + case[-1]+1]:
        x,y = map(int,data.split())
        matrix[x][y] = 1
    
    # 예외처리 구문으로 matrix가 없는 경우를 의미함.
    if not matrix:
        print(0)
    
    # 몇마리의 지렁이가 필요한지 count하기 위한 code시작
    count = 0 # 지렁이 수
    for x in range(len(matrix)): # x좌표
        for y in range(len(matrix[0])): # y좌표
            if matrix[x][y] == 1: # 해당 위치에 배추가 있으면  ~
                dfs(matrix,x,y) # 위에서 정의한 dfs를 돌려봄
                count += 1 # dfs함수에서 상하좌우를 다 돌려보고 오기에 count 1해서 지렁이수를 count
    ## case마다 지렁이수 print해줌
    print(count)

 

도서관에서 빌린 "파이썬 알고리즘 인터뷰" 책을 보면서 얻은 코드 이용해봄 !

해당 책 좋은 듯 👍