백준 14502 : 연구소

이틀전부터 본격적으로 dfs와 bfs를 접하기 시작했고, bfs 뿐만 아니라 bruteforce까지 함께 고려한 문제기 때문에 포스팅을 남기고자 한다.
(+ 혼자서 10분 딱 고민하고 골드문제 원솔로 푼건 처음이라 바로 포스팅하는건 비밀)

먼저, 문제의 세부 사항들을 살펴보았을때는 연구소의 벽을 3개 세워 바이러스의 감염을 최소화하는 알고리즘에 대해 막막함을 느낌과 동시에 조건들을 살펴보고, bruteforce로 충분히 풀 수 있겠다고 판단하였다.

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
시간 제한 : 2 초
메모리 제한: 512 MB

가장 먼저 그래프의 0인 부분들에 대해서 combination을 사용하여 3개를 선택하는 조합으로 그래프에 추가해주었다. 이때 각각의 경우의 수를 모두 고려하여 새롭게 그래프를 복사하고 해당 그래프 상에서 탐색을 진행해야 했기에 deepcopy를 사용하였다.

combination과 deepcopy의 코드는 다음과 같다.

import sys, copy
from itertools import combinations

# combination
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            wall_list.append( (i, j) )
        if graph[i][j] == 0:
            wall_candidate.append( (i, j) )

wall_comb = list(combinations(wall_candidate, 3))



#deepcopy
graph_ = copy.deepcopy(graph)

이어서 전체 노드 각각에 대해서 bfs를 돌리고(2 즉, 바이러스가 떨어져 있을 수 있기 때문에), 이때 이미 방문했거나, 벽, 2인 노드에 대해서는 pass하였다. 한번의 loop가 끝난 후에 그래프에서 0인 값을 count하여 저장하고, 저장된 count 값들 중 가장 큰 값을 찾는다면 벽 3개만으로 바이러스의 전파를 최소화 시켰을 때의 감염되지 않은 노드들의 수를 구할 수 있다.

전체 소스 코드는 다음과 같다.

import sys, copy
from itertools import combinations
from collections import deque

n, m = map(int, sys.stdin.readline().split())
graph = [ list(map(int, sys.stdin.readline().split())) for i in range(n)]

wall_list = []
#0인 노드들의 후보 리스트
wall_candidate = []

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            wall_list.append( (i, j) )
        if graph[i][j] == 0:
            wall_candidate.append( (i, j) )

#0인 노드들의 후보리스트에서 3개를 선택한 조합들의 리스트, 리스트의 길이는 len(wall_candidate) C 3
wall_comb = list(combinations(wall_candidate, 3))
#이동할 방향을 정의(상하좌우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(graph, x, y):
    global visited
    queue = deque()
    queue.append( (x, y) )
	
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
			# 주어진 노드의 범위를 벗어나는 경우
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
			# 벽을 만난 경우
            if graph[nx][ny] == 1:
                continue
			# 감염이 가능한 노드들은 2로 바꾸고 visited에 반영
            if graph[nx][ny] == 0:
                visited[nx][ny] = True
                graph[nx][ny] = 2
                queue.append( (nx, ny))

safe_zone = []
#임의의 3개 벽을 추가한 각각의 경우의 수들에 대해서
for comb in wall_comb:
	# 3개의 조합이 달라질때마다 기존의 그래프를 초기화 해야하므로 deep copy
    graph_ = copy.deepcopy(graph)
    for i in range(3):
        x, y = comb[i]
        #벽 추가
        graph_[x][y] = 1

    visited = [[False for i in range(m)] for j in range(n)]
    sum = 0
    for x in range(n):
        for y in range(m):
        	# bfs를 돌릴 조건을 충족하는 경우 : 아직 방문하지 않았으면서 2인 경우
            if not visited[x][y] and graph_[x][y] == 2:
                bfs(graph_, x, y)
	
    #감염이 안된 구역들 누적
    for i in range(n):
        for j in range(m):
            if graph_[i][j] == 0:
                sum += 1

    safe_zone.append(sum)

print(max(safe_zone))

이렇게 작성하고 나니 굉장히 누더기식 코드에 조금 부끄러워졌는데.....
포스팅할 글을 모두 작성한 후에, 다른 블로그들의 풀이 방식을 참고해보니 접근 방식이나 논리적 흐름이 비슷했다! (뿌듯) 추가로 삼성 SW 역량 테스트 기출문제라고 한다! 앞으로도 화이팅!