백준 알고리즘) 14502번 연구소 파이썬 !

오늘은 brute-force 알고리즘 완전 탐색 알고리즘 문제들을 풀었어요.

이것외에도 여러가지 테트로미노 , 일곱난쟁이 등등의 문제를 풀었는데

제가 직접 힌트나 검색없이 푸는데 성공한 문제가 이 문제라서 이 문제에 관해서

리뷰를 남기려고합니다.

아직 알고리즘에 미숙해서 최적화된 답은 아니겠지만 일단 맞았으니...

 

먼저 코드를 보여드릴게요

 

import sys
import copy
input=sys.stdin.readline
 
n,m=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(n)]
answerList=[]
 
def find_safty():
    global answerList
    current=copy.deepcopy(board)
    answer=0
    for i in range(n):
        for j in range(m):
            if current[i][j]==2:
                birus(i,j,current)
    for i in range(n):
        for j in range(m):
            if current[i][j]==0:
                answer+=1
    answerList.append(answer)
def birus(y,x,current):
    if(x+1<m and current[y][x+1]==0):
        current[y][x+1]=2
        birus(y,x+1,current)
    if(x-1>=0 and current[y][x-1]==0):
        current[y][x-1]=2
        birus(y,x-1,current)
    if(y+1<n and current[y+1][x]==0):
        current[y+1][x]=2
        birus(y+1,x,current)
    if(y-1>=0 and current[y-1][x]==0):
        current[y-1][x]=2
        birus(y-1,x,current)
def make_safty(index):
    if index==3:
        find_safty()
        return
    for i in range(n):
        for j in range(m):
            if board[i][j]==0:
                board[i][j]=1
                make_safty(index+1)
                board[i][j]=0
            else:
                continue
make_safty(0)
print(max(answerList))
 

조금 길죠 ??

1~7번째 줄은 처음 입력 값을 받고 필요한 것들을 import 해준 부분이에요.

copy는 바이러스 탐색중에 board값이 계속 유지되길래 복사한 board로 옮겨주기 위해 import 했습니다.

 

9~21 : answerList를 내부에서 외부까지 이어주기 위해 global 선언을 해주었고요.(안해도되나?)

current는 만들어진 board가 다음에 들어올 보드와 섞이지 않기 위해 현재 보드로 copy를 해주었습니다.

이제 아래 반복문에서 n행m열에서 바이러스인 '2'가 발견되면 birus가 옮겨가는 범위를 나타냄 함수인

birus()함수로 그 좌표와 현재 current 보드를 보내줍니다.

그렇게 모든 바이러스 '2'에 대해서 바이러스가 옮겨진 상태에서 남아있는 안전구역 '0'을 탐색해서 0이 있을때마다

answer값을 1 증가 해주었어요.

그다음 answerList에 append~

 

22~34: birus가 옮겨간 곳을 2로 current 보드를 바꿔주는 곳인데

처음에 인덱스 에러 때문에 try except를 사용해보았지만 뭐가 계속 안맞더라고요....문제점을 못찾아서 다른 방법으로

if문으로 바꿔서 사용했습니다

코드에서 일단 바이러스가 상하좌우 로만 이동이 가능하기때문에 2가 있는 좌표에서 

각각의 상하좌우를 탐색해서 만약 0이면 2로 바꿔주는 식으로 만들었습니다.

dx , dy로 나타내거나 그랬으면 더 코드가 간결해졌을 수도 있겠네요.

 

35~46: 완전 탐색인 만큼 일단 0인부분들 중에서 1을 3개씩 모두 넣는

코드로 해봤습니다.(13~14를 넣으니 버벅거리는 거보고 긴장했는데 시간초내에 통과되서 다행이였어요)

모든 부분을 탐색하며 1을 3개 넣으면 그값을 find safty 값으로 옮겨주고 다시 원래 코드로 돌리는 방식으로

만들었습니다. 이전 문제들 중에 비슷한 것들이 있어서 긴가민가 하면서 코드를 짜봤는데 잘 나오더라고요..!

 

마지막 두줄은 이제 만든 함수를 사용해주고 answerList에서 max값을 출력해주면

안전 구역의 최대 값이 나오더라고요.

 

어떤 식으로 굴러가야할지 머릿속에 생각은 금방 떠오르는데 항상 구현하는데 애를 먹네요...

빨리 이 문제 저 문제 풀어보면서 구현을 빠르게 할 수 있도록 다양한 경험을 해봐야할 것 같아요!