[DFS/BFS] 연구소 (BAEKJOON - 14502)

1. 문제

벽을 3개 지어서 0을 최대한 많이 만들어라.

virus는 상하좌우로 퍼짐

2. 입력

# SET - 1
N, M = 7, 7
maps = '''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'''

# SET - 2
N, M = 4, 6
maps = '''0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2'''

# SET - 3
N, M = 8, 8
maps = '''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. 출력

# SET - 1
result = 27

# SET - 2
result = 9

# SET - 3
result = 3

 

4. 풀이

나동빛 풀이를 보면, DFS로 푸는데 이를 똑같이 필사해서 백준에서 채점을 돌려보면, 시간초과가 뜬다.

(서버 문제일수도 있음.. 근데 구라안치고 너무 안풀려서 똑같이 필사함)

 

처음에 접근할 때

일단 N, M이 3~8로 크지 않기 때문에,

최악의 경우 (64C3) 41,664로 충분히 계산할 수 있는 범위라고 판단

완전탐색 + BFS로 접근했다.

 

사용 가능한 공간에서 Combinations로 3개를 뽑고

해당 wall의 좌표를 가져와 임시 맵을 생성*

 

bfs로 바이러스가 확산된 뒤 결과를 가지고 현재 사용 가능한 space를 계산한다.

 

사실 이렇게만 보면 되게 간단한 로직인데,

내부 구현을 어떻게 하냐에 따라 시간초과가 뜸

 

예를 들면, 처음에 2차원 배열로 만들지 않고,

virus 검사 부분에서 virus 좌표 in virus_list virus 좌표 in wall_list면 continue하게 했는데, 이렇게 하면 시간초과가 난다. 아무래도 virus_list 길이가 길어질수록 판단해야되는 길이가 길어지기 때문이기도 하고,

좌표먼저 범위 안에 있는지 검사한 뒤에 virus_list를 검사했어야 하는데

virus_list를 먼저 검사하고 좌표를 검사한것도 시간 초과에 한 몫 한 것 같다.

 

또한, 값을 복사할때 list.copy()나 copy의 deepcopy를 사용하면, 값이 제대로 복사가 안되거나 멘탈 붕괴할 수 있으니

맵과 크기가 같은 temp를 생성하고 for문을 2번 돌려 2차원 배열에 값을 하나씩 복사해주자.

N, M이 크면 어차피 완전탐색이나 이런 방식으로 푸는게 안되는 경우겠지..

 

따라서 신경써야 할 부분은,

1. list로 검사하기보다 2차원 행렬로 검사 (시간초과 발생 가능성)

2. copy보다 크기가 같은 temp 변수를 만들어 for문으로 값 복사 (내부 구조 때문)

 

5. 코드

from itertools import combinations
from collections import deque

N, M = map(int, input().split())
virus, walls, spaces, graph = [], [], [], []
for i in range(N):
    graph.append(list(map(int, input().split())))
    for j, v in enumerate(graph[i]):
        if int(v) == 2:
            virus.append((i, j))
        elif int(v) == 1:
            walls.append((i, j))
        else:
            spaces.append((i, j))

# bfs 확산
FOUR_DIR = [(-1, 0), (0, 1), (0, -1), (1, 0)]
def spread(temp_virus, temp_graph):
    q = deque()
    len_virus = len(temp_virus)
    for v in temp_virus:
        q.append(v)
    while q:
        i, j = q.popleft()
        for d_i, d_j in FOUR_DIR:
            next_i, next_j = i+d_i, j+d_j
            if 0 > next_i or next_i >= N or next_j < 0 or next_j >= M:
                continue
            else:
                if temp_graph[next_i][next_j] == 0:
                    temp_graph[next_i][next_j] = 2
                    len_virus += 1
                    q.append((next_i, next_j))
    return len_virus

def solution(N, M, virus, walls, graph, spaces):
    answer = 0
    temp = [[0]*M for _ in range(N)]
    for add_walls in combinations(spaces, 3):
        for i in range(N):
            for j in range(M):
                temp[i][j] = graph[i][j]
        for i, j in add_walls:
            temp[i][j] = 1
            
        result = N * M - spread(virus, temp) - len(walls) - 3
        answer = max(result, answer)
    
    print(answer)

solution(N, M, virus, walls, graph, spaces)