[알고리즘/구현] 14502번 : 연구소 - python

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

14502번: 연구소

---

• 문제
• 소요시간: 38분 10초

---

• 설계하기(접근방법) 

1. 입력받기

배열을 입력받는다

 

2. 구현하기

조합으로 풀면 되는 문제다

 

먼저 빈공간의 리스트를 뽑아낸다

그 후 그 빈공간 중 3개를 뽑는 조합 연산을 수행한다

 

각 bfs 시도마다

새로운 빈공간 3개씩을 집어넣어서

시뮬레이션을 돌린다

 

그 후 안전한 공간의 개수를

safe_zone 리스트에 넣는다

 

3. 출력하기

safe_zone에서의 max값을 출력한다

 

 

---

• 코드(출력)

from itertools import combinations
from collections import deque

n, m =  map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]

def bfs(p_lst):
    new_graph = [a[:] for a in graph]
    new_virus_location = deque([a[:] for a in virus_location])
    result = 0
    for i in p_lst:
        x, y =  empty_location[i]
        new_graph[x][y] = 1
    while new_virus_location:
        q = deque()
        q.append(new_virus_location.popleft())
        while q:
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<= nx < n and 0 <= ny < m:
                    if new_graph[nx][ny] == 0:
                        new_graph[nx][ny] = 2
                        q.append([nx,ny])
    for x in range(n):
        for y in range(m):
            if new_graph[x][y] == 0:
                result += 1
    return result

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

empty_location = []
virus_location = []

for x in range(n):
    for y in range(m):
        if graph[x][y] == 0:
            empty_location.append([x,y])
        if graph[x][y] == 2:
            virus_location.append([x,y])

num_list = [i for i in range(len(empty_location))]
p = list(combinations(num_list, 3))
safe_zone = []

for i in p:
    safe_zone.append(bfs(i))

print(max(safe_zone))

---

• 얻어갈 부분

1. 조합의 리스트를 먼저 숫자로만 뽑아내고 리스트 접근용으로 사용하여 코드를 깔끔하게 쓸 수 있었다