14502 - 파이썬

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

14502번: 연구소

---

내 풀이

 

from itertools import combinations

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

def virus(x, y):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    
    for k in range(4):
        xx = x+dx[k]
        yy = y+dy[k]
        if 0<=xx<n and 0<=yy<m and tmp[xx][yy] == 0:
            tmp[xx][yy] = 2
            virus(xx, yy)


def count():
    cnt = 0
    for i in range(n):
        for j in range(m):
            if tmp[i][j] == 0:
                cnt += 1
    return cnt


def solution():
    result = 0
    

    
    zeroIdxs = []
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                zeroIdxs.append((i, j))

    for coordinates in list(combinations(zeroIdxs, 3)):
        
        for x,y in coordinates:
            board[x][y] = 1

        
        for i in range(n):
            for j in range(m):
                tmp[i][j] = board[i][j]

        
        for i in range(n):
            for j in range(m):
                if tmp[i][j] == 2:
                    virus(i, j)

        result = max(result, count())
       
        for x,y in coordinates:
            board[x][y] = 0
    return result


print(solution())

---

이 문제 푸려고 진짜 오래고민했다. 거의 이주는 고민한듯..

근데 오늘 비슷한 유형의 문제를 풀면서 이해했다 드디어!

 

이 문제의 핵심이 무엇이냐

1) 벽을 세울 수 있는 모든 지점에 벽을 세운다. -> solution()을 통해

2) 바이러스를 모두 퍼뜨린다 -> virus() 을 통해

3) 넓이를 구한다.  -> count() 을 통해

4) 넓이를 구해서 최대값과 비교한다.  

5) 모든 경우의 수에 반복한다.

 

 

---

다른사람의 풀이

 

import sys
import copy
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(N)] # 그래프 생성
graph_copy = copy.deepcopy(graph) # 그래프 복사
dx, dy = [-1,1,0,0], [0,0,-1,1] # 상하좌우 이동

safe_region = 0 # 최대 안전 영역

# dfs
def dfs(x,y,sel_wall):
    sel_wall[x][y] = 2 # 바이러스로 변경

    # 상하좌우 탐색
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            if sel_wall[nx][ny] == 0: # 바이러스가 퍼질 수 있는 곳
                dfs(nx,ny,sel_wall) # 바이러스 퍼뜨리기


# 벽 선택하기
def select_wall(start, count):
    global safe_region

    if count == 3: # 벽이 3개 선택된 경우 실행
        sel_wall = copy.deepcopy(graph_copy) # 벽이 선택된 그래프 복사
        # dfs로 바이러스 퍼뜨리기
        for i in range(N):
            for j in range(M):
                if sel_wall[i][j] == 2: # 바이러스 발견시에 dfs
                    dfs(i,j,sel_wall)
        safe_count = sum(_.count(0) for _ in sel_wall) # 안전 영역 개수 계산
        safe_region = max(safe_region,safe_count) # 최대 안전 영역 개수 갱신
        return

    else: # 벽이 3개 선택되지 않은 경우
        for i in range(start, N*M): # 브루트-포스로 벽 선택
            r = i // M # M으로 나눈 몫는 행
            c = i % M # M으로 나눈 나머지는 열
            if graph_copy[r][c] == 0: # 해당 구역이 0인 경우에
                graph_copy[r][c] = 1 # 벽으로 선택
                select_wall(i,count+1) # 다음 벽 선택
                graph_copy[r][c] = 0 # 되돌리기

select_wall(0,0)
print(safe_region)

---

---

COMBINATION을 사용하지 않고도 풀이가 가능할거 같은데, 파이썬으로 돌리면 시간초과가 난다.

그 부분에 대해서는 조금 고민 해봐야 할거같다.