[백준/파이썬/삼성] 14502 파이썬 풀이

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

14502번: 연구소

 

문제 유형 : 구현 + dfs 

문제집에는 dfs로 분류되어 있었는데 구현 유형스러웠던 문제 ㅋㅋ

1. 벽을 설치한다 3개까지 -> board 2차원 배열 돌면서 board[i][j] == 0 이면 벽 설치 가능 

2. 3개 다 설치했으면 바이러스를 퍼뜨려 본다. 바이러스 퍼뜨릴 때 재귀호출해서 상하좌우 이동한다.

3. 바이러스를 퍼뜨린 후 안전지대를 계산한다.그리고 원래 가지고 있던 최대 안전지대 값이랑 비교하면서 최대 안전지대 결과 값을 구한다.

를 구현해보자 ㅋㅋ

n, m = map(int, input().split())
board = []
temp = [[0]*m for _ in range(n)] # 벽을 설치한 다음의 리스트

for i in range(n):
    board.append(list(map(int, input().split())))

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def virus(x,y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if temp[nx][ny] == 0 :
                temp[nx][ny] = 2
                virus(nx,ny)

def get_safe():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score += 1
    return score

result = 0

def dfs(count):
    global result
    if count == 3: # 외벽 설치 3개 했을 때 바이러스 퍼트려서 확인한다.
        for i in range(n):
            for j in range(m):
                temp[i][j] = board[i][j]
        
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i,j)
                    
        result = max(result, get_safe())

    # 외벽 설치하기 
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                count += 1
                board[i][j] = 1
                dfs(count)
                board[i][j] = 0
                count -= 1

dfs(0)
print(result)