[BJ14502] 연구소

🚩 문제 설명

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

14502번: 연구소

⏱️ 시간 복잡도
▪ 연구소의 벽을 세우는 행위 : 브루트포스 (N x N x N)
▪ 바이러스를 퍼트리면 (4 x N x M)
▪ 대충 O(N^5) 정도

◾ 연구소에 벽을 세워 바이러스를 막고, 총 안전영역의 최댓값을 찾는 문제입니다.

◾ 벽은 총 3개만 세워야한다는 점을 유의하시길 바랍니다.

◾ 시간은 2초 입니다. 1초에 연산을 1억개 정도 하므로, 2억개의 연산 아래서 계산이 되어야 합니다.

 

 

 

---

 

 

 

✅ 입출력

n m : 세로 x 가로

지도의 모양 : n개의 줄 (0: 빈칸, 1: 벽, 2: 바이러스)

return 안전영역 크기의 최댓값

✔️ 예제 1

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

✔️ 예제 2

4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2

9

✔️ 예제 3

8 8
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

3

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys
from collections import deque
from copy import deepcopy

#sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline
n, m = map(int, input().split())  # 세로 x 가로
mp = [list(map(int, input().split())) for _ in range(n)]  # 연구소맵

# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 큐 생성
q = deque()

# 벽 3개 세우기
def wall(cnt):
    global ans

    # 벽이 3개 세워진다면
    if cnt == 3:
        mp_ = deepcopy(mp)  # 원 배열 복사
        ans = max(ans, virus(mp_))
        return

    # 하나씩 벽 세워보기 : 브루트포스
    for i in range(n):
        for j in range(m):
            if mp[i][j] == 0:
                mp[i][j] = 1  # 벽 세우기
                wall(cnt + 1)
                mp[i][j] = 0  # 빠져나오면 다시 원 상태로


# 바이러스 퍼트리기
def virus(mp_):
    cnt = 0  # 안전영역의 수

    # 바이러스 위치 정보에서
    for x, y in v:
        q.append([x, y])

        while q:
            tmp = q.popleft()

            for i in range(4):  # 상하좌우 살피기
                x_ = tmp[0] + dx[i]
                y_ = tmp[1] + dy[i]

                if all([0 <= x_ <= n - 1, 0 <= y_ <= m - 1]):
                    if mp_[x_][y_] == 2:
                        continue

                    if mp_[x_][y_] == 0:
                        mp_[x_][y_] = 2
                        q.append([x_, y_])

    # 안전영역 세기
    for x in mp_:
        cnt += x.count(0)

    return cnt


if __name__ == '__main__':
    ans = 0  # 안전영역의 총 갯수 (0의 개수)

    # 바이러스 위치 저장
    v = []
    for i in range(n):
        for j in range(m):
            if mp[i][j] == 2:
                v.append([i, j])

    wall(0)
    print(ans)

💬 Point

1. 벽 3개를 세운다.
2. 바이러스를 퍼트린다.
3. 안전영역의 개수를 센다.

◾ pypy3 로 제출해야합니다. python3 로 제출하면 시간초과 에러가 납니다.

 

sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline
n, m = map(int, input().split())  # 세로 x 가로
mp = [list(map(int, input().split())) for _ in range(n)]  # 연구소맵

# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 큐 생성
q = deque()

◾ 필요한 수들을 입력 받습니다.

 

# 바이러스 위치 저장
v = []
for i in range(n):
    for j in range(m):
        if mp[i][j] == 2:
            v.append([i, j])

◾ 바이러스의 위치가 필요하므로, 반복문을 통해 바이러스 위치를 배열로 저장합니다.

 

# 벽 3개 세우기
def wall(cnt):
    global ans

    # 벽이 3개 세워진다면
    if cnt == 3:
        mp_ = deepcopy(mp)  # 원 배열 복사
        ans = max(ans, virus(mp_))
        return

    # 하나씩 벽 세워보기 : 브루트포스
    for i in range(n):
        for j in range(m):
            if mp[i][j] == 0:
                mp[i][j] = 1  # 벽 세우기
                wall(cnt + 1)
                mp[i][j] = 0  # 빠져나오면 다시 원 상태로

◾ 3개의 벽을 세우는 함수입니다. dfs() 를 이용하여 벽을 세웁니다.

만약 벽이 3개 세워진다면 바이러스를 퍼트리도록 합니다. 그리고 global 로 선언한 ans 와 개수를 비교하여 최댓값을 찾습니다.

벽을 세울 때는 브루트포스를 이용합니다.

벽을 세우고, 빠져나올떄는 다시 원상태로 만들어 줘야 합니다.

((0, 0), (0, 1), (0, 2)), ((0, 0), (0, 1), (0, 3)), ...  뭐 이런식으로 하나하나씩 따져가며 돈다고 볼 수 있습니다.

 

# 바이러스 퍼트리기
def virus(mp_):
    cnt = 0  # 안전영역의 수

    # 바이러스 위치 정보에서
    for x, y in v:
        q.append([x, y])

        while q:
            tmp = q.popleft()

            for i in range(4):  # 상하좌우 살피기
                x_ = tmp[0] + dx[i]
                y_ = tmp[1] + dy[i]

                if all([0 <= x_ <= n - 1, 0 <= y_ <= m - 1]):
                    if mp_[x_][y_] == 2:
                        continue

                    if mp_[x_][y_] == 0:
                        mp_[x_][y_] = 2
                        q.append([x_, y_])

    # 안전영역 세기
    for x in mp_:
        cnt += x.count(0)

    return cnt

◾ 바이러스를 셀 때는 bfs() 를 사용하여 셉니다.

바이러스 위치 정보를 저장한 배열을 돌면서 해당 타겟을 큐에 집어 넣습니다.

그리고나서 타겟을 하나씩 뺍니다.

해당 타겟의 상하좌우를 살펴 만약 주변이 0 이라면 큐에 집어넣습니다. 이런식으로 너비 탐색을 진행합니다.

주변에 맞닿은 것들이 계속 큐에 집어넣어져서 상하좌우를 살필 것입니다. 벽을 만나거나, 더이상 바이러스 감염 시킬 곳이 없다면 큐가 비어지게 되고 반복문을 그때 빠져나오게 됩니다.

마지막으로 해당 복사 배열에서 안전영역을 셉니다. 해당 안정영역을 센 수를 반환합니다.

반환된 값은 ans 와 비교되어 최댓값을 구하게 됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

# 알고리즘 백준 연구소 파이썬

# 알고리즘 백준 bj14502 연구소 python

---