[백준][Python] 14502번 : 연구소 ★

문제 출처 : www.acmicpc.net/problem/14502

14502번: 연구소

풀이 방법:

1. 벽을 3개 설치한 후

2. 모든 곳에 바이러스를 퍼트린 다음

3. 안전한 지역을 구해서 max값을 리턴한다

 

풀이 1은 돌려보면 값은 나오지만 시간초과로 실패를 하였다.

import sys
#sys.setrecursionlimit(10000)
#sys.stdin = open('./test.txt', 'r')
input = sys.stdin.readline

n,m = map(int,input().split())
data = [list(map(int,input().split())) for _ in range(n)]
temp = [[0]*m for _ in range(n)]

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

result = 0
# 모든 방향으로 바이러스 전파
def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx and nx < n and 0 <= ny and ny < m:
            if temp[nx][ny] == 0:
                temp[nx][ny] = 2
                virus(nx, ny)
            
# 안전 영역 크기 계산
def safe():
    cnt = 0
    for i in range(n):
        for j in range(m):
           if temp[i][j] == 0:
            cnt += 1
    return cnt

def dfs(count):
    global result
    # 울타리가 3개 설치된 경우
    if count == 3:
        # data를 temp에 넣어주고
        for i in range(n):
            for j in range(m):
                temp[i][j] = data[i][j]
        # 바이러스를 퍼트린 다음
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i,j)
        # 안전한 영역을 계산
        result = max(result,safe())
        return
        
    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1
                count += 1
                dfs(count)
                data[i][j] = 0
                count -= 1
dfs(0)
print(result)

그래서 다른 사람들의 풀이 방법을 보던 중  bcp0109.tistory.com/25이분꺼를 보게 되었다.

백준 14502번. 연구소 (Java, Python)

벽을 3개 세울 때 combination(조합)을 쓴다는 것인데 기존 1차원 배열이 아닌 2차원 배열에서 한다는 것이다.

너무나도 신기.. 오우

풀이1과 다른 점은 virusList를 따로 지정해 주었다는 점, copy라는 것을 새롭게 써보았다는 점. 가야할 길이 멀다.

import sys
import copy
#sys.setrecursionlimit(10000)
#sys.stdin = open('./test.txt', 'r')
input = sys.stdin.readline

n,m = 0, 0
data = []
result = 0
virusList = []
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


# 모든 방향으로 바이러스 전파
def virus(x, y, copyed):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx and nx < n and 0 <= ny and ny < m:
            if copyed[nx][ny] == 0:
                copyed[nx][ny] = 2
                virus(nx, ny, copyed)
          
# 안전 영역 크기 계산
def safe(temp):
    cnt = 0
    for i in range(n):
        for j in range(m):
           if temp[i][j] == 0:
            cnt += 1
    return cnt

def dfs(start, depth):
    global result
    # 울타리가 3개 설치된 경우
    if depth == 3:
        # data를 temp에 넣어주고
        temp = copy.deepcopy(data)

        # 바이러스를 퍼트린 다음
        for i in range(len(virusList)):
            [virusX, virusY] = virusList[i]
            virus(virusX, virusY,temp)

        # 안전한 영역을 계산
        result = max(result,safe(temp))
        return
        
    for i in range(start, n*m):
        x = (int)(i / m)
        y = (int)(i % m)

        if data[x][y] == 0:
            data[x][y] = 1
            dfs(i+1, depth+1)
            data[x][y] = 0

if __name__ == '__main__':
    n,m = map(int,input().split())
    for i in range(n):
        data.append(list(map(int,input().split())))

    for i in range(n):
        for j in range(m):
            if data[i][j] == 2:
                virusList.append([i,j])

dfs(0,0)
print(result)