백준 14502 - 연구소 (파이썬 python)

백준 14502 - 연구소 (파이썬 python)

14502번: 연구소

풀이 및 접근 방법

• 3개의 벽을 쌓는 경우의 수를 구하기 위해 조합을 썻고, 이를 위해 itertools 의 combinations를 사용했습니다.
• 3개의 벽을 세우는 경우의 수 마다 graph 변경을 하므로 원본 graph를 deepcopy한 graph_ 를 변화시켰으며, 이를 변화시킨 것으로 방문처리를 하였습니다. deepcopy를 위해 copy library를 사용했습니다.
• 최단거리를 구하라는 문제가 아니여서 dfs를 사용했습니다. (그러나 최단 거리를 구하는 문제가 아니더라도 bfs를 사용할 수 있습니다. 다른 분들의 풀이를 보니 이 문제에서 bfs 통한 풀이가 가능했습니다.)
• 다른 분들의 풀이를 보니 itertools를 사용하지 않고 3가지 벽을 세우는 경우를 구했는데 그 방법이 더 좋을 것 같습니다.

 

Code

import copy
from itertools import combinations

n,m = map(int,input().split())
# graph 생성
graph = []
for i in range(n):
    graph.append( list(map(int,input().split() )) )

# dfs 구현
def dfs(x,y):
    graph_[x][y] = 2
    
    for step in range(4):
        nx = x + dx[step]
        ny = y + dy[step]    

        if nx <= -1 or nx >=n or ny<=-1 or ny >=m:
            continue
        if graph_[nx][ny] != 0 :
            continue
        else:
            dfs(nx,ny)

# 이동 방향
dx = [-1,1,0,0]
dy = [0,0,1,-1]

# virus, zeros 위치 저장
virus = []; zeros = [ ]
for i in range(n) :
    for j in range(m):
        if graph[i][j] == 2:
            virus.append([i,j])
        elif graph[i][j] == 0:
            zeros.append([i,j])
            
# 3개의 벽이 세워질 수 있는 경우의 수 
zeros_combi = combinations(zeros, 3)

# 3개의 벽이 세워질 수 있는 경우의 수 마다 안전한 지역을 safety_zone_list에 저장
# for문이 끝나면 max(safety_zone_list) 통해 값 return
safety_zone_list = []
for combi in zeros_combi:
    graph_ = copy.deepcopy(graph)
    
    graph_[combi[0][0]][combi[0][1]] = 1
    graph_[combi[1][0]][combi[1][1]] = 1
    graph_[combi[2][0]][combi[2][1]] = 1
    
    for vi in virus :
        dfs(vi[0],vi[1])
        
    safety_zone = 0
    for row in range(n):
        for col in range(m):
            if graph_[row][col] == 0:
                safety_zone += 1

    safety_zone_list.append(safety_zone)
    
print(max(safety_zone_list))