14502 바이러스

1. 문제

문제는 링크를 들어가면 볼 수 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import copy
from collections import deque

N,M = map(int,input().split())
graph = []
for _ in range(N):
    graph.append(list(map(int,input().split())))

dx = [0 ,0, -1, 1] # 상 하 좌 우
dy = [-1 ,1 ,0, 0] # 상 하 좌 우

maximum = 0


def bfs():
    # 모든 바이러스를 detect하고 queue에 넣자
    q = deque()
    tmp_graph = copy.deepcopy(graph)
    for y in range(N):
        for x in range(M):
            if tmp_graph[y][x] == 2:
                q.append([y, x])

    while q:
        now = q.popleft()
        for j in range(4):
            ny = now[0] + dy[j]
            nx = now[1] + dx[j]

            if nx < 0 or ny < 0 or nx >= M or ny >= N:
                continue

            if tmp_graph[ny][nx] == 0:  # 아직 방문하지 않았다면
                q.append([ny, nx])
                tmp_graph[ny][nx] = 2

    global maximum


    cnt = 0
    for v in range(N):
        cnt += tmp_graph[v].count(0)
    maximum = max(maximum,cnt)

# 벽부터 만들어보자
def make_wall(cnt):
    if cnt == 3:
        bfs()
        return
    for a in range(N):
        for b in range(M):
            if graph[a][b] == 0:
                graph[a][b] = 1
                make_wall(cnt + 1)
                graph[a][b] = 0

make_wall(0)
print(maximum)

3. 문제 풀이

인터넷을 참고해서 푼 문제인데.. 이번에 또 새로운 개념을 배웠다. 백트래킹이란것.. 백준 알고리즘 분류에 있던데 다음주부턴 백트래킹도 한번 도전해봐야할 것 같다.

이 문제는 벽을 어디에 세울지 전혀 알수없는 문제다. 이럴땐 그리디로 접근해서 모든 경우를 살펴보는게 맞다. 그래서 벽을 3개를 아무곳이나 세우고 그때 BFS를 실행해서 0의 값이 몇개 있는지 확인한다. 그리고 현재의 최대값과 비교해서 더 큰 값을 갱신해주면 된다. 보다시피 반복문이 많기 때문에 시간이 오래 걸린다..