백준 14502번 파이썬 _ 연구소 (삼성기출)

www.acmicpc.net/problem/14502

14502번: 연구소

• 문제유형 : 그래프탐색 (DFS & BFS), 브루트포스 
• 문제풀이 :
  • 전체 로직은 다음과 같다.
    1. 주어진 연구소의 빈 공간 중 3개의 벽을 선택한다. By itertools의 combination
       • 조합라이브러리를 이용해 빈공간중에서 3개를 선택해서 배열에 저장하고, 이 배열을 돌면서 아래 2,3번 과정을 반복한다.
    2. 바이러스를 퍼뜨린다. By DFS (or BFS)
       • DFS를 이용해서 상하좌우로 이동하는데, 이때 지도를 넘어가진 않는지 체크해주며 이동한다.
       • 이동했을때 0인경우 (빈공간인경우) 감염시킨다. (여기서 카운트를 해준다.)
       • 세로(n) - y축 - 행(2차원배열의 0번째인자) / 가로(m) - x축 - 열 (2차원 배열의 1번째 인자)
    3. 안전구역의 개수를 센다. 
       • 2번과정에서 감염시킨 횟수를 처음 연구소의 빈공간에서 빼주고, 벽을세운 3도 빼준다.
  • 위 과정을 모든 경우에 대해 반복하면서(완전탐색) 안전구역의개수를 지금까지 중 가장 큰 값으로 갱신해 나간다.
  • 연구소의 크기가 최대 8*8이므로, 연구소의 크기가 최대일때 벽 3개를 고르는 모든 경우의 수를 다 해도 시간초과는 나지 않을것이라고 생각했다.
• 한마디
  • 문제를 보자마자 일단 브루트포스 (모든경우탐색) 이라고 생각해서 금방구현을 했다. 근데 마지막 케이스 (8*8)에서 시간초과가 날것같아서 괜히 예외처리에 고민을 하다가 뭔가 된것같아서 냇는데 맞았다.
  • 근데 예외처리 안해도 시간초과 안나고 그냥 맞는거였다. 
  • 파이썬에서 time으로 시간계싼하는거랑은 다르다는걸 이제 알았다. 바보..
• 정답코드 

import sys
import copy
from itertools import combinations
import time

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

n,m = map(int, input().split()) # 세로, 가로 - [n][m]

#0 - 빈칸, 1 - 벽, 2- 바이러스
graph = []
virus = []
emtpy = []
cases = []
zero_count = 0
virus_count = 0
wall_count = 0
visited = [ False * m for _ in range(n)]

for _ in range(n):
    line = list(map(int, input().split()))
    graph.append(line)

start = time.time()
for line in range(n):
    for one in range(m):
        curr = graph[line][one]
        if curr == 2:
            virus.append((line,one))
            virus_count +=1
        elif curr == 0:
            emtpy.append((line,one))
            zero_count += 1
        else:
            wall_count+=1

cases = list(combinations(emtpy, 3))

#상하좌우
dy = [1,-1,0,0] #n
dx = [0,0,-1,1] #m
count = 0



def dfs(graph, i):  # 2의 위치를 start인자로 넘긴다.
    global count
    for j in range(4):  # 상하좌우 이동하면서
        if 0 <= i[0] + dy[j] < n and 0 <= i[1] + dx[j] < m:  # 지도범위 안이면
            if graph[i[0] + dy[j]][i[1] + dx[j]] == 0:  # 빈공간이면
                graph[i[0] + dy[j]][i[1] + dx[j]] = 2  # 감염시킨다.
                count += 1 # 0이 없어진 개수
                dfs(graph, (i[0] + dy[j], i[1] + dx[j]))  # 새로 감염된 위치에서 재귀호출


# dfs(graph, (0,0)) #이후에 graph값이 바뀜
# print(graph)
# dfs(graph, (1,5))
# print(graph)

count_ = n*m
for case in cases:
    count = 0
    graph_temp = copy.deepcopy(graph)
    for i in case:  # case = ((1,2),(2,3),(3,4))
        graph_temp[i[0]][i[1]] = 1  # 3개를 벽으로 만든다.

    for j in virus:
        dfs(graph_temp, j)

    count_ = min(count, count_)

print(zero_count - count_ - 3)