[이것이 코딩테스트다] 9일차 - 백준 연구소

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 5 DFS/BFS

오늘 풀이한 문제

[백준 14502] 연구소

문제

- 바이러스(2)와 연결된 0을 오염시켜 2로 만들수 있다. 이때 현재 벽(1)에서 3개의 벽을 더 세워 최대한으로 살아남은 0의 개수를 센다

 

접근법

1. combinations를 사용해서 벽이 세워질 수 있는 모든 경우의 수를 구하자

2. 조합별로 bfs를 수행하고 0의 개수를 세자

- 이때 virus가 있는 부분에서만 bfs를 시작해서 실행시간을 단축하자!!

## input - 주피터에서 실험하기위해 미리 test case 입력

lab = [[2, 0, 0, 0, 1, 1, 0], 
       [0, 0, 1, 0, 1, 2, 0],
       [0, 1, 1, 0, 1, 0, 0],
       [0, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 1, 1],
       [0, 1, 0, 0, 0, 0, 0],
       [0, 1, 0, 0, 0, 0, 0]]

n, m = 7, 7 ## 지도의 세로, 가로
blank = []
virus = []

for i in range(n):
    for j in range(m):
        if lab[i][j] == 0: ## 바이러스가 퍼질 수 있는 공간
            blank.append((j,i))
        elif lab[i][j] == 2: ## 바이러스 위치
            virus.append((j,i))
            
from collections import deque

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

def bfs(): 
    queue = deque()
    for v in virus: ## 바이러스가 있는 곳에서만 bfs 실행
        queue.append(v)
        while queue:
            x,y = queue.popleft()
            for k in range(4):
                nx = x+dx[k]
                ny = y+dy[k] 

                if nx < 0 or nx >= n or ny < 0 or ny>= m:
                    continue

                if wall[nx][ny] == 0:
                    wall[nx][ny] = 2
                    queue.append((nx,ny))
    ## 살아남은 빈칸 카운트
    cnt = 0  
    for i in range(n):
        for j in range(m):
            if wall[i][j] == 0:
                cnt += 1
    return cnt
    
from itertools import combinations
import copy 

result = []
for combis in (combinations(blank, 3)):  ## 조합의 개수만큼 돈다
    wall = copy.deepcopy(lab)
    for x,y in combis:
        wall[x][y] = 1
    result.append(bfs())

max(result)

 

연습문제 풀이는 깃허브에도 업로드 되어있습니다 

GitHub - gymin97/algorithm_study: Solve the algorithm problems (python3)