문제

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

소스코드

from collections import deque
import copy
input = sys.stdin.readline

if __name__ == "__main__":
    n,m = list(map(int,input().split()))
    area = [list(map(int,input().split())) for _ in range(n)]
    
    def virus():
        dx = [1,-1,0,0]
        dy = [0,0,1,-1]
        tmp_area = copy.deepcopy(area)
        
        q = deque()

        for i in range(n):
            for j in range(m):
                if tmp_area[i][j] == 2:
                    q.append([i,j])
        while q:
            x,y = q.popleft()
            for k in range(4):
                xx = x + dx[k]
                yy = y + dy[k]
                if 0<=xx<n and 0<=yy<m and tmp_area[xx][yy]==0:
                      q.append([xx,yy])
                      tmp_area[xx][yy] = 2
        global result
        cnt = 0
        for i in range(n):
            cnt += tmp_area[i].count(0)
        result = max(cnt,result)


    def bfs(l):
        if l == 3:
            virus()
            return 
        
        for i in range(n):
            for j in range(m):
                if area[i][j]==0:
                    area[i][j] = 1
                    bfs(l+1)
                    area[i][j] = 0
    
    result = 0
    bfs(0)                
    print(result)

설명

생각한 로직

1. 벽을 세우는 모든 경우의 수를 확인한다 > 백트래킹 필요
2. 벽을 3개 세우면 2를 bfs해서 0을 2로 변경한다.
3. 0의 갯수를 체크해서 가장 많은 0을 return 한다.

후기

• 처음에 어떻게 접근해야할 지 감이 없었는데 일주일 뒤에 푸니까 풀이가 생각났다. 어떻게 할지 모르겠을 땐 냅다 브루트포스로 접근해보면 될거같다.. (다해봐랏..!) 그리고 전체 경우의 수도 문제를 보니까 조건이 (3 ≤ N, M ≤ 8)여서 많이 없음..^^;;ㅠㅠ
• pypy로 해야 시간초과가 나지 않는다.
• bfs에서 area를 탐색할 때 list는 mutable한 객체이므로 deep copy를 해줘야 독립적인 객체가 생성되어 탐색에 영향을 주지 않는다.
• 바이러스 탐색할 때 2가지 방법으로 탐색하였다.
  1. 방문했는지 안했는지 체크해서 탐색하는 방법

    def virus():
        dx = [1,-1,0,0]
        dy = [0,0,1,-1]
        tmp_area = copy.deepcopy(area)
        visited = [[0]*m for _ in range(n)]
        q = deque()

        for i in range(n):
            for j in range(m):
                if tmp_area[i][j] == 2:
                    q.append([i,j])
                    visited[i][j]=1
                    while q:
                        x,y = q.popleft()
                        for k in range(4):
                            xx = x + dx[k]
                            yy = y + dy[k]
                            if 0<=xx<n and 0<=yy<m and visited[xx][yy]==0 and tmp_area[xx][yy]==0:
                                q.append([xx,yy])
                                visited[xx][yy]=1
                                tmp_area[xx][yy] = 2
        global result
        cnt = 0
        for i in range(n):
            cnt += tmp_area[i].count(0)
        result = max(cnt,result)

2. 초반에 2를 q에 넣고 탐색하는 방법

    def virus():
        dx = [1,-1,0,0]
        dy = [0,0,1,-1]
        tmp_area = copy.deepcopy(area)
        
        q = deque()

        for i in range(n):
            for j in range(m):
                if tmp_area[i][j] == 2:
                    q.append([i,j])
        while q:
            x,y = q.popleft()
            for k in range(4):
                xx = x + dx[k]
                yy = y + dy[k]
                if 0<=xx<n and 0<=yy<m and tmp_area[xx][yy]==0:
                      q.append([xx,yy])
                      tmp_area[xx][yy] = 2
        global result
        cnt = 0
        for i in range(n):
            cnt += tmp_area[i].count(0)
        result = max(cnt,result)

2의 방법으로 탐색하는게 시간과 메모리를 적게 잡아먹는다