[백준] 14502번: 연구소 - python

문제 출처

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

14502번: 연구소

 

 

 

 

---

풀이 및 코드

문제를 살펴보면 완전 탐색이 가장 먼저 떠오른다. bfs/dfs로 가능한 모든 값을 찾으면 되지 않을까 하는 인사이트 문제를 파고 들었다.

문제를 살펴보면 3 <= n, m <= 8로 규모가 그리 크지 않음을 알 수 있다. 그렇다면 최대 칸수인 64를 bfs/dfs로 충분히 확인 할 수 있다는 의미이다.

 

 

필자는 벽을 어떻게 세우는 것이 효율적인가 에 대해 고민을 해 보았다. 필자는 비효율적일 것이다라고 답을 내렸다 특정 지점들을 선택해 안전영역을 계산할 수 있다면 보다 빠르게 값을 도출할 수도 있겠지만 그 과정을 코드로 작성하며 여러 값들을 저장하고 판단하는 과정이 시간소요가 오래 걸릴 것이라고 판단했다. 결정적으로 앞서 말한 바와 같이 해당 문제의 입력 데이터 크기가 작아 가능한 모든 경우의 수를 살펴보아도 시간초과가 걸리지 않을 것이라고 판단했다.

 

따라서 바이러스 확산이 가능한 모든 곳에서 3곳을 선정해 벽을 세우고 안전지역을 계산하도록 코드를 구현하였다.

 

---

 

먼저 데이터 전처리 부분이다. virus는 list로 안전 구역은 개수를 저장해 주었다.

r, c = map(int, input().split())
lab = []
virus = []
safe = 0
for rr in range(r):
    lab.append(list(map(int, input().split())))
    for cc in range(c):
        if lab[rr][cc] == 2:
            virus.append([rr,cc])
        elif lab[rr][cc] == 0:
            safe += 1

 

오염구역은 bfs와 deque를 이용해서 찾았다. 오염구역들을 list로 반환하도록 코드를 작성하였다.

dx = [0,0,-1,1]
dy = [-1,1,0,0]
def bfs(lab):
    polluted = []
    dq = deque(virus)
    while dq:
        y, x = dq.popleft()
        for d in range(4):
            ny = y + dy[d]
            nx = x + dx[d]
            if 0 <= ny < r and 0 <= nx < c and lab[ny][nx] == 0:
                polluted.append([ny, nx])
                dq.append([ny, nx])
                lab[ny][nx] = 3
     
    return polluted

 

 

벽을 설치할 3개의 지점 선정은 iterations.combination을 매서드를 사용하였다. 파이썬은 모듈이 많아서 참 편하다ㅎ

new_lab = copy.deepcopy(lab)
polluted = bfs(new_lab)

n = len(polluted)
for comb in combinations(polluted, 3):
    new_lab = copy.deepcopy(lab)
    for y, x in comb:
        new_lab[y][x] = 1
    
    new_polluted = bfs(new_lab)
    n = len(new_polluted) if len(new_polluted) < n else n
    
print(safe - 3 - n)

 

 

 

---

전체코드