[백준] 14502번 연구소- 파이썬

 

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

14502번: 연구소

from itertools import combinations
import sys
import copy
from collections import deque
n,m = map(int,sys.stdin.readline().split())
room = []
for _ in range(n):
    room.append(list(map(int,sys.stdin.readline().split())))

wall = []
virus = []
for i in range(n):
    for j in range(m):
        if room[i][j] == 0:
            wall.append([i,j])
        if room[i][j] == 2:
            virus.append([i,j])
wall =list(combinations(wall,3))
no_virus_room = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def bfs(x,y, graph):
    queue = deque()
    queue.append((x,y))
    while queue:
        x, y =queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx <0 or ny <0 or nx >= n or ny >= m:
                continue
            if graph[nx][ny] == 1:
                continue
            if graph[nx][ny] == 0:
                graph[nx][ny] = 2
                queue.append((nx,ny))
    return graph

for i in range(len(wall)):
    count = 0
    new = copy.deepcopy(room)
    a, b = wall[i][0]
    c, d = wall[i][1]
    e, f = wall[i][2]
    new[a][b] = 1
    new[c][d] = 1
    new[e][f] = 1
    for j in range(n):
        for k in range(m):
            if new[j][k]== 2:
                new = bfs(j,k,new)
    for j in range(n):
        for k in range(m):
            if new[j][k]== 0:
                count+=1
    no_virus_room = max(count,no_virus_room)
print(no_virus_room)

미친 풀이를 했다 그냥 아무 조합으로 벽 만들곳 정하고 

그냥 bfs로 퍼트린다음 세는 법으로 했는데 맞기는 했다 너무 오래 걸리기는한데;

다른 풀이 사람들 어캐 풀었는지좀 봐야겠다.

 

찾아 봤는데 나쁘지 않은 풀이였다...?! ㅋㅋ