[알고리즘 일기] 165. 연구소

문제 165. (2022-01-26)

 

14502번: 연구소

Baekjoon 14502. 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

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

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

---

입력

• 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
• 둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
• 빈 칸의 개수는 3개 이상이다.

---

출력

• 첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

---

❧ 입력 예시

7 7
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

❧ 출력 예시

27

---

❧ 정답

 

🔎IDEA) 지도의 범위가 최대 8x8 형태이므로 나올 수 있는 모든 지도의 형태를 조합으로 뽑아서 dfs를 적용한다!

[Line 10]
👉 빈칸('0')인 칸에만 벽을 설치할 수 있으므로, 입력받은 지도에서 값이 '0'인 칸들의 위치만 좌표값을 zeros 리스트에 튜플 형태로 담는다.
👉 해당 0의 좌표 값들 중 무작위로 3개를 뽑는 조합을 생성해서 comb 리스트에 담는다.
이때 리스트의 값은 [((a, b), (c, d), (e, f)) ... ((g, h), (i, j), (k, l))] 의 형태가 된다!

 

[Line 18]
👉 dfs 코드
: dx : 상하이동, dy : 좌우이동

• 상하좌우를 이동하며 그래프 범위를 벗어나는 경우, 해당 부분은 건너뛴다.
• 만약 이동한 좌표가 빈칸('0')일 경우 바이러스를 퍼뜨리고 해당 위치에서 다시 dfs를 재개한다.

 

[Line 30]
👉 이전에 뽑은 조합 리스트 comb 에서 조합 하나에 대한 맵을 생성한다.
이때, 원래 입력으로 받은 리스트를 복사한 뒤 조합 하나에 대한 벽을 생성해야하므로, 깊은 복사 copy.deepcopy() 메서드를 이용하여 원래 리스트의 값이 변경되지 않도록한다.
Reference

12. 얕은 복사(shallow copy)와 깊은 복사(deep copy)

👉 새로 생성된 맵을 돌면서 바이러스가 있으면 ('2') 해당 부분을 시작으로 바이러스를 퍼뜨린다. -> dfs 재귀 메서드 수행
👉 전체 지도에 대한 탐색을 마친 뒤, 최종 지도에서의 빈칸('0')의 개수를 해서 cnt 값에 더한다.
만약, 해당 지도에서 나온 개수가 최대값일 경우 최종 결과값 rst 의 값을 갱신한다.

 

❧ 답안 예시

Reference : [나동빈, 『이것이 코딩테스트다 with 파이썬』, 한빛미디어(2020), 531p]

n, m = map(int, input().split())
data = []  # 초기 맵 리스트
temp = [[0] * m for _ in range(n)]  # 벽을 설치한 뒤의 맵 리스트

for _ in range(n):
    data.append(list(map(int, input().split())))

# 4가지 이동 방향에 대한 리스트
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

result = 0

# 깊이 우선 탐색(DFS)을 이용해 각 바이러스가 사방으로 퍼지도록 하기
def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 상, 하, 좌, 우 중에서 바이러스가 퍼질 수 있는 경우
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if temp[nx][ny] == 0:
                # 해당 위치에 바이러스 배치하고, 다시 재귀적으로 수행
                temp[nx][ny] = 2
                virus(nx, ny)

# 현재 맵에서 안전 영역의 크기를 계산하는 메서드
def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score += 1
    return score

# 깊이 우선 탐색(DFS)을 이용해 벽을 설치하면서 매번 안전 영역의 크기 계산
def dfs(count):
    global result
    # 벽이 3개 설치된 경우
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = data[i][j]
        # 각 바이러스의 위치에서 전파 진행
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i, j)
        # 안전 영역의 최댓값 계산
        result = max(result, get_score())
        return
    # 빈 공간에 벽 설치
    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1
                count += 1
                dfs(count)
                data[i][j] = 0
                count -= 1


dfs(0)
print(result)

• 전체 조합을 따로 구하지 않고 dfs 메서드를 두어, 벽 설치 및 바이러스 전파 과정을 반복함