[Python] 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개 이상이다.

📌 출력

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

📌 문제 풀이

👨‍🏫 접근

벽을 세운다는 것이 솔직히 감이 쉽게 잡히지 않았다. 특별한 규칙성이 보이지 않았기 때문이다. 그런데 벽의 개수가 3개라는 점이 의문점이었다. 왜 굳이 3개일까? 이것은 사실 시간 복잡도 때문이었다. 특별한 규칙성이 없었기 때문에 완전 탐색으로 벽을 하나하나 다 세워가면서 풀이하는 방법을 사용해야 한다. 그래서 벽을 3개만 세울 수 있는 것이다.

이렇게 할 수 있는 것은 가로와 세로의 크기가 8로 크지 않은 수이기 때문이다. 그렇게 때문에 완전 탐색으로 맵의 모든 곳을 돌아다니면서 값을 찾을 수 있는 것이다.

재귀를 통해서 모든 벽을 세우고 그 다음 바이러스를 모두 퍼뜨린 다음 그 지도를 2중 for문으로 탐색하면 된다.

👨‍🏫 문제 풀이

📄 전체 코드

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]
visited_lab = [[0] * m for _ in range(n)]
visited_wall = [[0] * m for _ in range(n)]

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

ans = 0
def bfs():
    global ans

    q = deque()

    # 바이러스 위치 파악하여 퍼질 수 있는 곳 체크
    for x in range(n):
        for y in range(m):
            # visited_lab[x][y]가 0이기만 하면 방문하지 않은 것이니까 그냥 값을 저장
            visited_lab[x][y] = graph[x][y]
            if graph[x][y] == 2:
                q.append((x, y))
                visited_lab[x][y] = 1

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            # 방문한 좌표가 이미 방문했거나 바이러스거나 벽이 아니라면
            if 0 <= nx < n and 0 <= ny < m and not visited_lab[nx][ny]:
                visited_lab[nx][ny] = 1
                q.append((nx, ny))

    temp = 0
    for x in range(n):
        for y in range(m):
            if not visited_lab[x][y]:
                temp += 1

    ans = max(ans, temp)

def bt(depth, _x):
    if depth == 3:
        bfs()
        return

    for x in range(_x, n):
        for y in range(m):
            if not graph[x][y] and not visited_wall[x][y]:
                visited_wall[x][y] = 1
                graph[x][y] = 1
                bt(depth + 1, x)
                visited_wall[x][y] = 0
                graph[x][y] = 0

bt(0, 0)
print(ans)

📄 준비

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]
visited_lab = [[0] * m for _ in range(n)]
visited_wall = [[0] * m for _ in range(n)]

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

ans = 0

필요한 라이브러리와 모듈을 불러오고 맵과, 방문테이블 2개를 만든다. 첫째는 실험실에서 안전 영역을 체크하기 위한 방문 테이블이고 둘째는 벽을 만들기 위한 방문테이블이다.

📄 풀이

def bfs():
    global ans

    q = deque()

    # 바이러스 위치 파악하여 퍼질 수 있는 곳 체크
    for x in range(n):
        for y in range(m):
            # visited_lab[x][y]가 0이기만 하면 방문하지 않은 것이니까 그냥 값을 저장
            visited_lab[x][y] = graph[x][y]
            if graph[x][y] == 2:
                q.append((x, y))
                visited_lab[x][y] = 1

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            # 방문한 좌표가 이미 방문했거나 바이러스거나 벽이 아니라면
            if 0 <= nx < n and 0 <= ny < m and not visited_lab[nx][ny]:
                visited_lab[nx][ny] = 1
                q.append((nx, ny))

    temp = 0
    for x in range(n):
        for y in range(m):
            if not visited_lab[x][y]:
                temp += 1

    ans = max(ans, temp)

def bt(depth, _x):
    if depth == 3:
        bfs()
        return

    for x in range(_x, n):
        for y in range(m):
            if not graph[x][y] and not visited_wall[x][y]:
                visited_wall[x][y] = 1
                graph[x][y] = 1
                bt(depth + 1, x)
                visited_wall[x][y] = 0
                graph[x][y] = 0

bt(0, 0)
print(ans)

두 개의 파트로 나눠서 bfs와 백트래킹을 설명하고자 했는데 백트래킹이 어렵지 않아서 함께 설명한다.

먼저 백트래킹 부분이다.

---

def bt(depth, _x):
    if depth == 3:
        bfs()
        return

    for x in range(_x, n):
        for y in range(m):
            if not graph[x][y] and not visited_wall[x][y]:
                visited_wall[x][y] = 1
                graph[x][y] = 1
                bt(depth + 1, x)
                visited_wall[x][y] = 0
                graph[x][y] = 0

bt(0, 0)
print(ans)

Base Condition으로 벽을 3개를 세웠을 때 bfs를 불러온다.

2중 for문으로 그래프를 순회한다. 그래프 상에서 그 좌표가 빈 곳이며 방문한 적이 없을 때, 백트래킹을 사용한다. x에서 _x로 시작하는 이유는 어차피 이전 x 좌표는 과거에 방문한 곳이기 때문에 다시 방문하여 시간 소요를 늘릴 필요가 없기 때문이다.

---

def bfs():
    global ans

    q = deque()

    # 바이러스 위치 파악하여 퍼질 수 있는 곳 체크
    for x in range(n):
        for y in range(m):
            # visited_lab[x][y]가 0이기만 하면 방문하지 않은 것이니까 그냥 값을 저장
            visited_lab[x][y] = graph[x][y]
            if graph[x][y] == 2:
                q.append((x, y))
                visited_lab[x][y] = 1

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            # 방문한 좌표가 이미 방문했거나 바이러스거나 벽이 아니라면
            if 0 <= nx < n and 0 <= ny < m and not visited_lab[nx][ny]:
                visited_lab[nx][ny] = 1
                q.append((nx, ny))

    temp = 0
    for x in range(n):
        for y in range(m):
            if not visited_lab[x][y]:
                temp += 1

    ans = max(ans, temp)

2중 for문으로 graph를 복사한다. 만약 그 곳에 바이러스가 있으면 바이러스 좌표를 큐에 저장하고 미리 방문처리한다. 이후 while 반복을 시작한다.

visited 테이블에서는 0이 아니면 안전 영역이 모두 아니므로 방문처리하여 안전영역을 없앤다. 2로 저장해도 상관은 없다.

temp 변수로 안전영역을 세고 최댓값을 갱신한다.

📌 총평

왜 골드5인지 모르겠다 더 높아도 될 것 같은데?