14502 - 연구소*

2022. 5. 3. 13:572022/BaekJoon_삼성 SW 역량 테스트 기출

#import sys
#input = sys.stdin.readline().rstrip()
def virus(x, y):
    tx, ty = 0, 0
    for i in range(4):
        tx = x + dx[i]
        ty = y + dy[i]
        if (0<=tx<N) and(0<=ty<M):
            if temp[tx][ty] == 0:
                temp[tx][ty] = 2
                virus(tx, ty)

def score():
    score = 0
    for i in range(N):
        for j in range(M):
            if temp[i][j] == 0:
                score+=1
    return score

def dfs(wall):
    global maxSize
    
    if wall == 3:
        for i in range(N):
            for j in range(M):
                temp[i][j] = graph[i][j]
                
        for i in range(N):
            for j in range(M):
                if temp[i][j] == 2:
                    virus(i, j)

        
        size = score()
        maxSize = max(maxSize, size)
        return 
    
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 0:
                graph[i][j] = 1
                wall += 1
                dfs(wall)
                graph[i][j] = 0
                wall -= 1

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
maxSize = 0; graph = []
N, M = map(int, input().split())
temp = [[0]*M for _ in range(N)]
for _ in range(N):
    MList = list(map(int, input().split()))
    graph.append(MList)
    
dfs(0)
print(maxSize)

'2022 > BaekJoon_삼성 SW 역량 테스트 기출' 카테고리의 다른 글

14888 - 연산자 끼워넣기  (0) 2022.05.03
14503 - 로봇청소기*  (0) 2022.05.03
14501 - 퇴사*  (0) 2022.05.03
14500 - 테트로미노*  (0) 2022.05.03
13458 - 시험감독  (0) 2022.05.03