[BOJ] 14502. 연구소

문제

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

14502번: 연구소

 

 

 

---

 

주요 아이디어

굉장히 기초적인 BFS 문제이다.

기본적인 아이디어는 다음과 같다

 

• 빈 칸 중 벽을 세울 칸 3개의 좌표를 조합으로 뽑아낸다.
  • 문제 조건 중 "무조건 3개의 벽"을 세우라고 했기 때문에 별다른 예외처리는 안해도 된다
• 조합 순회를 돌면서 벽을 세우고, 해당 벽을 세웠을 때 바이러스가 전파된 경우를 확인한다
  • 바이러스 전파는 bfs 방식으로 체크한다
  • 원본이 바뀌는 것을 막기 위해 bfs 진행 시마다 map을 deepcopy 한다

 

---

 

코드 구현 (Python 3)

 

from itertools import combinations
from collections import deque
import copy

# 입력받기
n, m = map(int, input().split())
lab = [[] for _ in range(n)]

for i in range(n):
    lab[i] = input().split()

empty = []
virus = []

for i in range(n):
    for j in range(m):
        if lab[i][j] == '0':
            empty.append([i, j])
        elif lab[i][j] == '2':
            virus.append([i, j])

# 3개의 벽을 세울 모든 조합 경우의 수
combi = list(combinations(empty, 3))

# 바이러스 전파 후 최종 안전 영역 넓이
def check_safety_area(lab):
    cnt = 0
    for i in range(len(lab)):
        for j in range(len(lab[0])):
            if lab[i][j] == '0':
                cnt += 1
    
    return cnt


def bfs(lab):
    direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    queue = deque()
    
	# virus 순회하면서 시작 좌표로 넣기
    for v in virus:
        queue.append(v)
    
    while queue:
        i, j = queue.popleft()

        # 인접 노드 방문
        for d in direction:
            ni, nj = i + d[0], j + d[1]
            if 0 <= ni < len(lab) and 0 <= nj < len(lab[0]) and lab[ni][nj] == '0':
                queue.append([ni, nj])
                # 방문 처리 -> 바이러스 전파
                lab[ni][nj] = '2'

    return check_safety_area(lab)


result_list = []

for c in combi:
    # 벽 세우기
    lab_copy = copy.deepcopy(lab)
    for wall in c:
        lab_copy[wall[0]][wall[1]] = '1'
    
    # 바이러스 리스트 시작좌표로 넣고 bfs 돌리기
    result_list.append(bfs(lab_copy))

# 모든 가벽 경우의 수 중 가장 안전영역 넓이 넓은 경우
print(max(result_list))

 

 

 

 

제출 결과

---

 

코드 개선 방안

코드가 왠지 좀 길어보인다.. 만 내가 푼 코드 중에서 시간 & 공간 복잡도가 가장 낮았다

개인적인 스타일로 코드가 좀 길어보이더라도 저렇게 각 기능마다 함수를 구별해주는 편이 이해하기 편한 것 같다!