14502번. 연구소

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

 

 

이 문제는 DFS or BFS 이기도 하고, 완전 탐색이기도 하다. 

더 힌트를 주자면 두 번의 DFS 나 BFS 를 사용해야 한다.

 

코드를 실행 순서대로 보자.

 

n, m = map(int, sys.stdin.readline().split())  # n=세로 m=가로
lab = []
for _ in range(n):
    lab.append(list(map(int, sys.stdin.readline().split())))
    
virusList = []
virusInit, wallInit = count_num(virusList)

maxSafe = 0

set_wall(0, 0)

1~4번 줄은 데이터 입력을 받는 부분이다.

6번줄의 virusList는 초기에 바이러스(2)인 위치를 저장하는 리스트이다. 토마토를 익히는 문제를 생각해보자.

초기에 익은 상태인 토마토들을 리스트에 따로 담아서, 익히는 과정(BFS)을 시작할 때 큐의 초기값으로 넣어줬었다.

바이러스가 확산되는 것이나 토마토가 익는 것이나 같은 행동이나 마찬가지이므로 익은 토마토처럼 바이러스를 따로 저장해주었다.

7번 줄은 문제의 정답인 안전지대 갯수를 구하기 위해서 따로 변수를 선언한 것인데, 나는 (전체 지역-벽 갯수-바이러스 갯수=안전지대 갯수) 로 구했기 때문에 변수를 저렇게 받아왔다. 안전지대 갯수를 구하는 방법은 나중에 이중 for문을 돌려서 0을 구해도 되고 자기 마음이기 때문에 count_num() 함수를 따로 쓰지는 않겠다.

9번 줄의 maxSafe는 최종 정답이 될 안전지대 갯수이다.

이제 다음으로 호출되는 set_wall 함수를 보자.

 

 

# startR을 인자로 넣어줌으로써 해당 row 보다 이전 row 들은 선택하지 않도록 한다. (중복 선택 방지)
def set_wall(count, startR):
    if count == 3:
        spread_virus()
        return

    for r in range(startR, n):
        for c in range(m):
            if lab[r][c] == 0:  # 아무것도 없으면 벽으로 선택
                lab[r][c] = 1
                set_wall(count+1, r)
                lab[r][c] = 0

set_wall은 벽을 선택하는 함수이다. 그런데 어디서 많이 본 양식이다. 바로 조합 문제이다. N과 M (2) 참고

처음 호출할 때 set_wall(0, 0) 으로 호출했는데 이 의미는 '현재 0개의 벽을 선택했고, 0번째 row부터 보자'라는 의미이다.

N과 M (2)를 풀 때도 마찬가지였다. 조합은 순서가 없으므로 한 번 선택한 것은 다시 볼 필요가 없다. 따라서 현재 인덱스를 기억하기 위해서 row를 인자로 넘겨준 것이다.

잘 생각해보면 N과 M 은 일차원 리스트였으므로 인덱스 하나만 저장했었다. 이 문제는 이차원 리스트이다. 그럼 row와 column을 다 저장해야 하나? 그건 아닌게, column 까지 기억해버리면 안된다.

예를 들어

1	2	3
4	5	6
7	8	9

라는 행렬에서 저 함수대로 3개를 조합으로 선택해야 된다고 쳐 보자.

[1, 2, 3]을 선택한 후 [1, 2, 4]를 선택해야 되는데 column에 제한을 걸었으므로 [1, 2, 5]를 선택하게 된다. 

만약 중복을 최대한 줄이고 싶다면 같은 row일 때는 해당 column 보다 작은 값들은 선택하지 않도록 해야 정확히 그 조합 갯수만큼 선택할 수 있다. 2차원 배열에서 조합 선택하기

 

 

 

그 다음, 벽을 3개 선택했을 때 호출되는 spread_virus 함수를 보자.

# bfs
def spread_virus():
    global maxSafe
    queue = collections.deque()
    queue.extend(virusList)  # 처음에 바이러스가 있었던 자리들로 초기화
    visited = [[0 for _ in range(m)] for _ in range(n)]
    virus_spread = virusInit  # 바이러스 갯수 = 초기 바이러스 갯수 (점차 더해갈 것임)

    while queue:
        row, col = queue.popleft()
        for r, c in [[row+1, col], [row-1, col], [row, col+1], [row, col-1]]:
            if 0 <= r < n and 0 <= c < m:
                if visited[r][c] == 0:
                    visited[r][c] = 1
                    if lab[r][c] == 0:
                        virus_spread += 1
                        queue.append([r, c])
    maxSafe = max(maxSafe, (n * m) - wallInit - virus_spread)
    return virus_spread

바이러스를 전염시키는 것은 토마토를 익히는 것과 비슷해서 bfs를 썼지만 토마토와는 달리 최단 경로를 구하는 것이 아니므로 dfs를 사용해도 무방할 것 같다.

바이러스를 초기 큐로 잡은 후, 바이러스는 상하좌우로 움직일 수 있으므로 경로 탐색하는 것처럼 상하좌우에 있는 노드들을 큐에 넣고, 방문(탐색)했을 시에는 재탐색하지 않도록 1로 체크한다.

0을 만나면 전염시킬 수 있는 것이므로 virus_spread 에 1을 더한다. 그리고 안전 지대 최댓값을 구한다.

큐가 없어지면 전염 시킬 수 있는대로 다 시킨 것이므로 바이러스 갯수를 리턴한다.

 

 

이제 이 문제의 알고리즘 설명은 다 끝났다고 볼 수 있다. 사실 이 문제를 처음 풀 때는 벽을 선택하는 함수까지도  visited 리스트를 만들고 상하좌우로 이동하는 것처럼 만들었다. 하지만 그렇게 할 필요가 없는게 우선 벽은 (0, 0)부터 (n, m)까지 순차적으로 선택해서 세우면 된다. 바이러스처럼 상하좌우로 움직이는 것이 아닌 것이다. (그렇게해도 결국엔 다 탐색하겠지만..) 그리고 둘째로, 벽은 3개가 되면 거기서 멈추고 바이러스를 퍼트리는 함수로 넘어가야 하므로 백트래킹의 형식을 띠고 있다고 볼 수 있다. 복잡복잡하게 경로 탐색 형식으로 만들어도 되긴 하겠지만 읽기도 불편하고 추가적인 연산이 더 필요할 것이다. 

 

 

 

다음은 코드 전문이다.

import sys
import collections


def count_num(lst):
    w = 0
    v = 0
    s = 0
    for r in range(n):
        for c in range(m):
            if lab[r][c] == 2:
                v += 1
                lst.append([r, c])
            elif lab[r][c] == 1:
                w += 1
    return v, w + 3  # 세워질 3개의 벽까지 포함


# bfs
def spread_virus():
    global maxSafe
    queue = collections.deque()
    queue.extend(virusList)  # 처음에 바이러스가 있었던 자리들로 초기화
    visited = [[0 for _ in range(m)] for _ in range(n)]
    virus_spread = virusInit

    while queue:
        row, col = queue.popleft()
        for r, c in [[row+1, col], [row-1, col], [row, col+1], [row, col-1]]:
            if 0 <= r < n and 0 <= c < m:
                if visited[r][c] == 0:
                    visited[r][c] = 1
                    if lab[r][c] == 0:
                        virus_spread += 1
                        queue.append([r, c])
    maxSafe = max(maxSafe, (n * m) - wallInit - virus_spread)
    return virus_spread


# startR을 인자로 넣어줌으로써 해당 row 보다 이전 row 들은 선택하지 않도록 한다. (중복 선택 방지)
def set_wall(count, startR):
    if count == 3:
        spread_virus()
        return

    for r in range(startR, n):
        for c in range(m):
            if lab[r][c] == 0:  # 아무것도 없으면 벽으로 선택
                lab[r][c] = 1
                set_wall(count+1, r)
                lab[r][c] = 0


n, m = map(int, sys.stdin.readline().split())  # n=세로 m=가로
lab = []
for _ in range(n):
    lab.append(list(map(int, sys.stdin.readline().split())))
virusList = []
virusInit, wallInit = count_num(virusList)

maxSafe = 0

set_wall(0, 0)

print(maxSafe)