Python/brute-force BOJ-14502 연구소

Posted on | In

[Python/brute-force] BOJ-14502 연구소

안전 영역 크기의 최댓값을 구하는 문제다.

  1. 벽을 어떻게 세울까?
  2. 어떻게 안전한 지역을 탐색할까?

brute-force로 벽을 세우고, dfs로 바이러스를 퍼트린 후 안전영역을 체크한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import copy 

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

# 상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

max_ans = 0

def virus(x,y,sel_graph) :
    sel_graph[x][y] = 2 
    for i in range(4) :
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M :
            if sel_graph[nx][ny] == 0 :
                virus(nx,ny,sel_graph)

# 벽세우고 - 바이러스 퍼트리고 - 안전영역 세기
def wall(start, cnt) :
    global max_ans
    if cnt == 3 :
        sel_graph = copy.deepcopy(graph)
        for x in range(N) :
            for y in range(M) :
                if sel_graph[x][y] == 2 :
                    virus(x,y,sel_graph)
        safe_region = sum(_.count(0) for _ in sel_graph)
        max_ans = max(max_ans, safe_region)
        return
    else :
        for i in range(start, N*M):
            x = i // M
            y = i % M
            if graph[x][y] == 0 :
                graph[x][y] = 1
                wall(i, cnt+1)
                graph[x][y] = 0

wall(0,0)
print(max_ans)

Reference

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

풀이참고 : https://deep-learning-study.tistory.com/619

회고

조금만 꼬아놓으면, 길을 잃어버린다.. ಥ_ಥ 갈길이 멀다.