백준 14502 연구소 파이썬

www.acmicpc.net/problem/14502

14502번: 연구소

import copy
import sys
import itertools
from collections import deque

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    graph = []

    for _ in range(N):
        graph.append(list(map(int, sys.stdin.readline().split())))

    all_walls = []
    comb_temp = []

    for i in range(N):
        for j in range(M):
            comb_temp.append((i, j))

    all_walls = list(itertools.combinations(comb_temp, 3))

    def bfs(q, t_graph):
        direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while q:
            now = q.popleft()
            if t_graph[now[0]][now[1]] == 2:
                for d in direction:
                    nv, nh = now[0] + d[0], now[1] + d[1]
                    if nv < 0 or nv >= N or nh < 0 or nh >= M:
                        continue

                    if t_graph[nv][nh] == 0:
                        t_graph[nv][nh] = 2
                        q.append((nv, nh))


    max_safety_count = 0
    for f,s,t in all_walls:
        temp_graph = copy.deepcopy(graph)
        if temp_graph[f[0]][f[1]] != 0 or temp_graph[s[0]][s[1]] != 0 or temp_graph[t[0]][t[1]] != 0:
            continue

        # 벽 세우기
        temp_graph[f[0]][f[1]] = 1
        temp_graph[s[0]][s[1]] = 1
        temp_graph[t[0]][t[1]] = 1

        virus_queue = deque()
        for j in range(N):
            for k in range(M):
                if temp_graph[j][k] == 2:
                    virus_queue.append((j, k))

        bfs(virus_queue, temp_graph)
        safety_count = 0
        for l in range(len(temp_graph)):
            for m in range(len(temp_graph[0])):
                if temp_graph[l][m] == 0:
                    safety_count+=1
        max_safety_count = max(max_safety_count, safety_count)
    print(max_safety_count)

# 7 7
# 2 0 0 0 1 1 0
# 0 0 1 0 1 2 0
# 0 1 1 0 1 0 0
# 0 1 0 0 0 0 0
# 0 0 0 0 0 1 1
# 0 1 0 0 0 0 0
# 0 1 0 0 0 0 0

 

문제 자체가 그렇게 어렵게 느껴지진 않았는데 고생은 좀 했다. 

어떤 문제는 어떻게 풀어야할지 감이 전혀안잡히고 막막한게 있는데 이건 보는 순간 풀수있겠단 생각이 들었다

우선 이 문제의 핵심 아이디어는 벽을 3개 세우는 모든 경우의 수에 대하여 바이러스를 퍼뜨린 후, 그 중 안전지대가 가장 많은 경우를 찾아내는것이다.

이 문제는 DFS 또는 BFS 로 풀 수 있는데 나는 BFS 로 풀었다.

1. N*M 배열의 모든 지점 (i, j)를 임시 배열에 담는다.

2. itertools 의 combinations 를 사용하여 모든 지점 배열에서 세군데의 지점을 선택하는 모든 경우의 수를 구한다.

3. 세군데의 지점이 선택된 배열을 순회하면서 세군데 지점이 모두 안전지대가 아니면 벽을 설치할 수 없는 지점이므로 무시한다.

4.  세군데가 모두 안전지대라면 벽을 설치한다.

5. 현재 그래프에서 바이러스가 있는 지점을 deque 에 담고, 이 지점에서 bfs로 바이러스를 퍼뜨린다.

6. 바이러스가 다 퍼진 후, 안전지대의 갯수를 센다. 이전 최대 안전지대 보다 현재 안전지대가 크다면 최대 안전지대의 값을 변경한다.

 

** 벽을 세우는 매 경우마다 처음 입력받은 그래프에서 진행을 해야하므로 매 경우마다 그래프를 복사했다.

처음에는 temp_graph = graph[:] 으로 하였으나, graph 가 2차원 list 이므로 얕은 copy 로는 안된다.

temp_graph 의 2차원 리스트의 값이 변경되면 graph의 값도 같이 변경되기 때문에 매 경우마다 이전 경우에 간섭을 받게된다. (이 부분에서 약간 시간을 소모 하였고 combinations 로 벽 3개를 세우는 모든 경우의 수를 구하는 부분에서 시간을 많이 지체했다. combinations 를 처음 사용해보았기때문.)

 

잘 풀어내서 뿌-듯.