[삼성 SW 역량테스트 기출] 백준 14502번 연구소

문제 링크 : https://www.acmicpc.net/problem/14502

난이도 : 골드 4

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개 설치할 수 있는 경우에 대해서 다 고려해봐야한다.

그리고 그 중 가장 안전영역(0)의 개수가 최대인 경우를 찾으면 된다. 

 

즉, 완탐으로 문제를 해결해야하는데 시간 초과 없이 풀 수 있을까??

 

입력값의 범위를 보면 연구소의 크기는 최대 8x8 까지 가능하다. 

그리고 바이러스는 2개 이상이여야한다. 

 

최악의 경우는 64-2 = 62개의 빈칸 중 3개의 벽을 설치할 수 있는 공간을 선택하는 조합이므로 62C3일 것이다. 

이는 천만번보다 작은 숫자이기 때문에 시간제한은 2초이지만 1초 안에도 충분히 풀 수 있는 문제이다.

 

나의 풀이 

다음과 같은 순서로 bfs를 사용하였다.

 

1. itertools를 사용해서 벽을 설치할 수 있는 모든 조합 저장

2. 각 조합마다 벽을 설치, bfs로 바이러스 퍼뜨리기

3. 안전영역(0의 개수) 계산하여 저장

4. 가장 큰 안전영역 개수 출력

 

dfs 문제는 bfs로도 대부분 풀리기 때문에 일단 bfs로 지르고 보는 편^..^ (사실 dfs 재귀는 넘 어려워서 아직 잘 못풀겠음ㅎ)

주의할 점은 각 경우마다 연구소 맵이 달라지기 때문에 초기화 해줄 수 있는 행렬을 만들어줘야한다. (이것때메 오류가 났다.. 밥오)

from itertools import combinations
from collections import deque

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

# bfs로 바이러스 전파
def bfs(x,y, temp) :
    q = deque([(x,y)])

    while q :
        cx, cy = q.popleft()
        for i in range (4) :
            nx, ny = cx + dx[i], cy + dy[i]
            if nx < 0 or nx > n-1 or ny < 0  or ny > m-1 or temp[nx][ny] == 1 or temp[nx][ny] == 2:
                continue
            else : 
                temp[nx][ny] = 2 
                q.append((nx, ny))


n, m = map(int, input().split())
lab, safe, virus = [], [], []
temp = [[0] * m for _ in range(n)] # 매번 달라지는 map을 처리해주는 행렬 초기화
results = []

for x in range(n) :
    data = list(map(int, input().split()))
    for y in range (m) :
        if data[y] == 0 :
            safe.append((x,y))
        elif data[y] == 2:
            virus.append((x,y))
    lab.append(data)

walls = []
# 가능한 조합 검사
for i in combinations(safe, 3):
    walls.append(i)

for wall in walls :
    safecnts = 0 # 0의 개수
    # 맵 정보 복사
    for i in range (n) :
        for j in range(m) :
            temp[i][j] = lab[i][j] # temp = lab은 안된다.
    #  가능한 조합을 순회하며 벽 설치
    for w in range(3) :
        wx, wy = wall[w][0], wall[w][1]
        temp[wx][wy] = 1
    for v in virus :
        vx, vy = v[0], v[1]
        bfs(vx, vy, temp) # 바이러스 퍼트리기
    # 매 조합마다 안전영역(0)의 개수 세서 정보 저장
    for i in range (n) :
        for j in range(m):
            if temp[i][j] == 0 :
                safecnts+=1
    results.append(safecnts)

# 가장 큰 값 출력
print(max(results))

 

 

또 주의해야할 점 ! 리스트를 복사할 때는 temp = lab과 같이 단순히 = 를 써서 하면 안된다.  (이거때메 또 오류ㅜ..)

리스트는 일반 int, float,.. 등등의 객체와는 다른 mutable한 성질을 가지고 있기 때문에 리스트 복사를 하게 되면

실제로 list는 1개만 존재하지만 포인터는 2가지 이름으로 가리키는 것이다. 

따라서 temp를 수정하면 기존의 lab 행렬에도 반영이 되어버린다.

 

그렇기 때문에 리스트를 그대로 복사하는 것이 아니라 이중 for loop로 돌면서 원소를 하나하나 복사 해야한다.

(deep copy 모듈을 사용하는 방법도 있는데 기업마다 코테에서 copy 모듈을 사용할 수 있을지는 모르겠다.)

 

 

해설 풀이

이코테 책의 dfs 문제 풀이 방법은 다음과 같다. 

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

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

#dfs로 바이러스 전파
def virus(x,y) :
    for i in range (4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx < n and 0<= ny < m :
            if temp[nx][ny] == 0:
                temp[nx][ny] = 2
                virus(nx, ny) # 인접한 영역에 바이러스 전파


# 현재 맵에서 안전 영역(0)의 개수 계산
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] #매번 경우의 수마다 temp에 복사하여 초기화 해줘야함
        
        # 설치된 벽에 따라 바이러스 전파
        for i in range(n) :
            for j in range(m) :
                if temp[i][j] == 2:
                    virus(i,j)

        result = max(result, get_score())
        return
    
    # dfs로 벽 설치
    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)

 

 

여기서는 itertools 모듈 없이 dfs로 벽을 설치하고, 바이러스를 전파하는 방법을 사용하고 있다.

만약 itertools 모듈 허용이 안된다면,, dfs로 모든 조합, 가능한 경우의 수를 따져볼 수 밖에 없는듯 ???

백트래킹을 여기서 쓰는구나.. 연습 많이많이 하자ㅠㅠ

 

나는 최대값을 구하기 위해서 모든 경우에 대한 안전영역 값을 리스트에 저장해서 가장 큰 수를 뽑아냈는데,

풀이에서는 result 값을 갱신하면서 max값 비교로 훨씬 간결하게 나타내고 있다.

괜히 리스트 하나 더 만들지 말고,, 이 방법도 잘 활용할 것 .. ✏️

 

 

+) 확실히 bfs가 빠르긴 한가보다. python3로 dfs 해설풀이 제출하니까 시간초과 뜸.. pypy3로 해야 통과된다.

 

 

오늘 문제 덕분에 잊고 있었던 파이썬 문법 다시 짚어볼 수 있었다!!~ 같은 실수하지말기!