[BOJ] 14502 - 연구소

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

14502번: 연구소

import sys
n, m = map(int, input().split())
graph = [list(map(int, sys.stdin.readline().rstrip().split())) for i in range(n)]
temp = [[0] * m for i in range(n)]
cnt = 0
result = 0

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

def virus(x, y):
    if temp[x][y] == 2:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            
            if temp[nx][ny] == 0:
                temp[nx][ny] = 2
                virus(nx, ny)            
                

def dfs(cnt):
    num = 0
    global result
    if cnt == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = graph[i][j]
        
        for i in range(n):
            for j in range(m):
                virus(i, j)
                
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 0:
                    num += 1
        result = max(result, num)
        return
        
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                cnt += 1
                dfs(cnt)
                graph[i][j] = 0
                cnt -= 1
                            
    
dfs(cnt)
print(result)

이 문제의 풀이 방법은

1. 벽 3개를 설치하는 모든 경우의 수를 계산한다.
2. 모든 경우의 수에 대해서 바이러스를 퍼뜨린 후 각각 안전 영역의 크기를 구한다. 

def dfs(cnt):
    num = 0
    global result
    if cnt == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = graph[i][j]
        
        for i in range(n):
            for j in range(m):
                virus(i, j)
                
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 0:
                    num += 1
        result = max(result, num)
        return
        
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                cnt += 1
                dfs(cnt)
                graph[i][j] = 0
                cnt -= 1

1번의 경우는 이 문제에서 n과 m의 크기가 그렇게 크지 않기 때문에 백트래킹으로 완전 탐색하면서 모든 경우의 수를 구해줄 수 있다. 위의 코드는 벽 3개를 설치하는 모든 경우의 수를 구하는 함수이다. 벽의 개수가 3이 되기 전까지 재귀함수를 통해 벽을 선택하다가 벽이 3개되면 바이러스를 퍼뜨린 후 안전 영역의 크기를 구한 뒤 백트래킹 되어 빈칸으로 돌아온다. 

 

바이러스를 퍼뜨리는 함수는 일반적인 DFS / BFS 를 사용하여 구현할 수 있었다.

---

보충

처음 풀어본 골드 문제였다. 아이디어를 떠올리는 것은 그렇게 어렵지 않았지만 구현하는 과정이 어려웠다.

벽 세우는 함수에서 백트래킹 부분은 결국 정답 코드를 참고할 수 밖에 없었다.

 

처음 생각했던 방법은 3중 for 문으로 완전 탐색을 하는 방법이었는데 도저히 구현이 안되서 포기했었는데 다른 블로그를 보다 보니 그렇게 구현하신 분이 있어서 코드를 가져와봤다. 

for i in range(len(empty_list)):
	for j in range(i):
		 for k in range(j):
			 y1, x1 = empty_list[i]
			 y2, x2 = empty_list[j]
			 y3, x3 = empty_list[k]
			
			 g[y1][x1] = WALL
			 g[y2][x2] = WALL
			 g[y3][x3] = WALL

			 ng = copy.deepcopy(g)
			 bfs(ng)

			 g[y1][x1] = EMPTY
			 g[y2][x2] = EMPTY
			 g[y3][x3] = EMPTY

출처: https://cotak.tistory.com/14 [TaxFree]

 

또한 다른 분의 코드에서 처음부터 빈칸의 좌표를 리스트로 따로 저장해두고  파이썬의 조합 라이브러리를 이용하여 벽을 3개 선택하는 모든 경우의 수를 구하는 테크닉이 있다는 것을 깨달았다.

 

---

느낀 점

백준 사이트에서  Python 3을 통해 컴파일하니 시간 초과를 받아서 PyPy3을 통해 컴파일 해보니 정답 판정을 받았다. 

이런 경우가 있다고는 들었는데 직접 겪어보니 조금 당황스러웠다.