[백준] 연구소 14502 (Python)

문제 링크

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

나의 풀이 방법

1. 안전영역인 0의 좌표들을 safe_zones배열에 저장한다.
2. 3개의 벽을 세울 안전영역 3군데를 고른다.
   1. 이때 (1,1), (2,2), (3,3)에 세우는 것과 (1,1), (3,3), (2,2)에 세우는 것은 똑같은 경우이기 때문에, combination을 사용한다.
   2. 이 작업을 하지 않으면 시간초과가 발생한다.
3. 안전영역에 3개의 벽을 세우는 모든 경우의 수에 대해 bfs를 수행한다.

 

Code

# 연구소

import sys
from collections import deque
from itertools import combinations
input = sys.stdin.readline

row, col = map(int, input().split())

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

graph = []
safe_zones = []
virus_zones = []

result = 0

for i in range(row):
    graph.append(list(map(int, input().split())))

# 벽을 3개 세울 때 중복되는 조합 없게 하기 위해 combination 사용
# ex) (1,1) (2,4) (3,5) 세우고 검사한 뒤 나중에 (2,4) (1,1) (3,5)를 방지하기 위해
for i in range(row):
    for j in range(col):
        if graph[i][j] == 0:
            safe_zones.append([i, j])
        if graph[i][j] == 2:
            virus_zones.append([i,j])

def bfs(tmp_graph):
    q = deque(virus_zones)

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < row and 0 <= ny < col:
                if tmp_graph[nx][ny] == 0:
                    tmp_graph[nx][ny] = 2
                    q.append((nx,ny))

    global result

    count = 0

    for i in range(row):
        for j in range(col):
            if tmp_graph[i][j] == 0:
                count += 1

    result = max(result, count)

def wall():
    safe_zones_combi = combinations(safe_zones, 3)

    for walls in safe_zones_combi:
        a, b, c = walls[0], walls[1], walls[2]

        graph[a[0]][a[1]] = 1
        graph[b[0]][b[1]] = 1
        graph[c[0]][c[1]] = 1

        tmp_graph = [item[:] for item in graph]

        bfs(tmp_graph)

        graph[a[0]][a[1]] = 0
        graph[b[0]][b[1]] = 0
        graph[c[0]][c[1]] = 0

wall()

print(result)

Git

https://github.com/youngh0/Algorithm/blob/master/DFS%2CBFS/boj_14502.py