[백준] 연구소 - Python

로그인

POINT

dfs (깊이 우선 탐색)

바이러스가 있는 곳(2)을 기준으로, 주변에 바이러스를 퍼뜨린다.

→ 바이러스 주변 칸의 값이 0이면 2로 바꾸고 주변을 계속 탐색한다. (방문 처리)

풀이

1. 새로운 벽을 3개 세운다.

2. 바이러스를 퍼뜨린다.

3. 안전 지역의 최댓값을 계산한다.

4. 모든 곳에 벽을 세워 볼 때까지 1 ~ 3을 반복한다.

from itertools import combinations

n, m = map(int, input().split())
graph = [[0] * m for _ in range(n)]
new_graph =[[0] * m for _ in range(n)] # 복사한 그래프
blanks = [] # 빈칸 위치를 넣은 리스트

for r in range(n):
    data = list(map(int, input().split()))
    for c in range(m):
        graph[r][c] = data[c] # 그래프 정보 저장
        if data[c] == 0:
            blanks.append((r,c)) # 빈칸 좌표 저장
            
new_walls = combinations(blanks, 3) # 3개의 벽을 세우는 경우의 수

# 벽을 3개 세운다.
def add_new_walls(graph, walls):
    for r, c in walls:
        graph[r][c] = 1

# 빈칸인 곳에 바이러스를 퍼뜨린다.
def dfs(graph, x, y):
    # 그래프 범위를 벗어나면 종료
    if x < 0 or x >= n or y < 0 or y >= m:
        return
    
    # 빈 칸이면 바이러스 퍼뜨리기
    if graph[x][y] == 0:
        graph[x][y] = 2 # 방문 처리
        dfs(graph, x-1, y)
        dfs(graph, x+1, y)
        dfs(graph, x, y-1)
        dfs(graph, x, y+1)

# 안전 지역의 크기를 반환한다.
def get_size(graph):
    result = 0
    for r in range(n):
        for c in range(m):
            if graph[r][c] == 0:
                result += 1

    return result
    
answer = 0
for case in new_walls:
    # 그래프 복사
    for r in range(n):
        for c in range(m):
            new_graph[r][c] = graph[r][c]
    
    add_new_walls(new_graph, case) # 벽 세우기
    
    for x in range(n):
        for y in range(m):
            # 바이러스가 있으면 주변으로 퍼뜨리기
            if new_graph[x][y] == 2:
                dfs(new_graph, x-1, y)
                dfs(new_graph, x+1, y)
                dfs(new_graph, x, y-1)
                dfs(new_graph, x, y+1)
    
    area = get_size(new_graph) # 안전 지역 크기 구하기                
    answer = max(answer, area) # 최댓값 갱신

print(answer)