[Boj/백준] 14502 Python

문제출처: https://www.acmicpc.net/problem/14502

14502번: 연구소

 

 

1. 문제 접근 방식

처음에는 어떻게 할지 막막하다가 케이스가 적기때문에 브루트포스로 풀기로 했다.

0의 개수를 combination으로 받아 벽을 세울 수 있는 케이스의 개수를 구한다.

for문을 순회하면서 2에 대해서 BFS를 수행한다.

 

 

2. 내가 푼 코드

import sys
from collections import deque
from itertools import combinations
import copy

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


n, m = map(int,sys.stdin.readline().split())

graph = []

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



zero_list = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            zero_list.append([i,j])

comb_zero_list = list(combinations(zero_list,3))

def bfs(x,y):
    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 nx>=n or ny<0 or ny>=m:
                continue
            if temp_graph[nx][ny] == 0:
                queue.append((nx,ny))
                temp_graph[nx][ny] = 2
arr=[]
for comb in comb_zero_list:
    count = 0
    temp_graph = copy.deepcopy(graph)
    temp_graph[comb[0][0]][comb[0][1]] = 1 
    temp_graph[comb[1][0]][comb[1][1]] = 1
    temp_graph[comb[2][0]][comb[2][1]] = 1
    
    for i in range(n):
        for j in range(m):
            if temp_graph[i][j] == 2:
                bfs(i,j)
    
    for i in range(n):
        for j in range(m):
            if temp_graph[i][j] == 0:
                count+=1

    arr.append(count)

print(max(arr))

 

 

3. 결과 및 느낀점

처음에 어떻게 풀지 몰라서 막막했는데

DFS&BFS문제에는 브루트포스를 자주 사용하는 것 같다.

케이스가 적다면 당황하지말고 모든 경우의 수 다 체크하자.

그래프의 원소들이 계속 바뀌면 deepcopy를 해주자.