이번 문제는 삼성 기출 문제로 BFS를 이용한 구현으로 해결하였다. 우선 Combinations를 사용해야 한다는 생각을 하였고, itertools를 이용하여 Combinations를 사용하여 해결해본 후에, Combinations를 재귀함수로 직접 구하여 다시 해결해보았다. 안전지대의 최대값을 구하는 로직은 다음과 같이 구현하였다.

• n, m을 입력받는다.
• grid를 입력받는다.
• dy, dx에 상하좌우 방향을 저장한다.
• road에 0으로 표시된 좌표를 모두 담는다.
• 감염된 구역을 표시하는 함수 bfs를 r, c를 인자로 갖도록 선언한다.
  -> q를 deque로 선언한다.
  -> q에 (r, c)를 넣는다.
  -> visited[r][c]를 True로 갱신한다.
  -> q가 존재하는 동안 반복하는 while문을 돌린다.
  --> y, x를 q에서 추출한다.
  --> 4번 반복하는 i에 대한 for문을 돌린다.
  ---> ny, nx를 y+dy[i], x+dx[i]로 선언한다.
  ---> 만약 ny가 0 이상, n 미만이고, nx가 0 이상, m 미만이고, visited[ny][nx]가 False이고, tmp[ny][nx]가 1이 아닐 경우,
  ----> visited[ny][nx]를 True로 갱신한다.
  ----> tmp[ny][nx]를 2로 갱신한다.
  ----> q에 (ny, nx)를 넣는다.
• 안전 지역을 구하는 함수 get_safe를 r, c를 인자로 갖도록 선언한다.
  -> q를 deque로 선언한다.
  -> q에 (r, c)를 넣는다.
  -> visited[r][c]를 True로 갱신한다.
  -> 안전 지역의 넓이를 저장할 변수 result를 1으로 선언한다.
  -> q가 존재하는 동안 반복하는 while문을 돌린다.
  --> y, x를 q에서 추출한다.
  --> 4번 반복하는 i에 대한 for문을 돌린다.
  ---> ny, nx를 y+dy[i], x+dx[i]로 선언한다.
  ---> 만약 ny가 0 이상, n 미만이고, nx가 0 이상, m 미만이고, visited[ny][nx]가 False이고, tmp[ny][nx]가 0일 경우,
  ----> visited[ny][nx]를 True로 갱신한다.
  ----> q에 (ny, nx)를 넣는다.
  ----> result를 1 증가시킨다.
  -> result를 반환한다.
• comb에 combinations의 결과를 넣는다.
• 결과를 저장할 리스트 answers를 선언한다.
• comb의 길이만큼 반복하는 i에 대한 for문을 돌린다.
  -> answer를 0으로 선언한다.
  -> 임시 리스트 tmp에 grid를 복사한다.
  -> 방문처리 리스트 visited를 False로 채운다.
  -> comb[i]에 저장된 좌표 3개를 tmp에서 1로 바꿔준다.
  -> n번 반복하는 i에 대한 for문을 돌린다.
  --> m번 반복하는 j에 대한 for문을 돌린다.
  ---> 만약 tmp[i][j]가 2이고, visited[i][j]가 False일 경우,
  ----> bfs(i, j)를 호출한다.
  -> n번 반복하는 i에 대한 for문을 돌린다.
  --> m번 반복하는 j에 대한 for문을 돌린다.
  ---> 만약 tmp[i][j]가 0이고, visited[i][j]가 False일 경우,
  ----> answer를 get_safe(i, j)의 반환값만큼 증가시킨다.
  -> answers에 answer를 담는다.
• answers의 최댓값을 출력한다.

Code

itertools.combinations를 이용한 풀이

from itertools import combinations
from copy import deepcopy
from collections import deque
n, m=map(int, input().split())
grid=[list(map(int, input().split())) for _ in range(n)]
dy, dx=[1, 0, -1, 0], [0, 1, 0, -1]
road=[]
for i in range(n):
    for j in range(m):
        if grid[i][j]==0:
            road.append((i, j))
def bfs(r, c):
    q=deque()
    q.append((r, c))
    visited[r][c]=True
    while q:
        y, x=q.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<n and 0<=nx<m and not visited[ny][nx] and tmp[ny][nx]!=1:
                visited[ny][nx]=True
                tmp[ny][nx]=2
                q.append((ny, nx))
def get_safe(r, c):
    q=deque()
    q.append((r, c))
    visited[r][c]=True
    result=1
    while q:
        y, x=q.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<n and 0<=nx<m and not visited[ny][nx] and tmp[ny][nx]==0:
                visited[ny][nx]=True
                q.append((ny, nx))
                result+=1
    return result
comb=list(combinations(road, 3))
answers=[]
for i in range(len(comb)):
    answer=0
    tmp=deepcopy(grid)
    visited=[[False for _ in range(m)] for _ in range(n)]
    for j in range(len(comb[i])):
        tmp[comb[i][j][0]][comb[i][j][1]]=1
    for i in range(n):
        for j in range(m):
            if tmp[i][j]==2 and not visited[i][j]:
                bfs(i, j)
    for i in range(n):
        for j in range(m):
            if tmp[i][j]==0 and not visited[i][j]:
                answer+=get_safe(i, j)
    answers.append(answer)
print(max(answers))

재귀함수를 통해 combinations를 구현한 풀이

from copy import deepcopy
from collections import deque
n, m=map(int, input().split())
grid=[list(map(int, input().split())) for _ in range(n)]
dy, dx=[1, 0, -1, 0], [0, 1, 0, -1]
road=[]
for i in range(n):
    for j in range(m):
        if grid[i][j]==0:
            road.append((i, j))
def get_comb(road, r):
    comb=[]
    if r==0:
        return [[]]
    for i in range(len(road)):
        tmp=road[i]
        road_tmp=road[i+1:]
        for j in get_comb(road_tmp, r-1):
            comb.append([tmp]+j)
    return comb
def bfs(r, c):
    q=deque()
    q.append((r, c))
    visited[r][c]=True
    while q:
        y, x=q.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<n and 0<=nx<m and not visited[ny][nx] and tmp[ny][nx]!=1:
                visited[ny][nx]=True
                tmp[ny][nx]=2
                q.append((ny, nx))
def get_safe(r, c):
    q=deque()
    q.append((r, c))
    visited[r][c]=True
    result=1
    while q:
        y, x=q.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<n and 0<=nx<m and not visited[ny][nx] and tmp[ny][nx]==0:
                visited[ny][nx]=True
                q.append((ny, nx))
                result+=1
    return result
comb=get_comb(road, 3)
answers=[]
for i in range(len(comb)):
    answer=0
    tmp=deepcopy(grid)
    visited=[[False for _ in range(m)] for _ in range(n)]
    for j in range(len(comb[i])):
        tmp[comb[i][j][0]][comb[i][j][1]]=1
    for i in range(n):
        for j in range(m):
            if tmp[i][j]==2 and not visited[i][j]:
                bfs(i, j)
    for i in range(n):
        for j in range(m):
            if tmp[i][j]==0 and not visited[i][j]:
                answer+=get_safe(i, j)
    answers.append(answer)
print(max(answers))