난이도 : ●●○ | 풀이 시간 : 40분 | 시간 제한 : 2초 | 메모리 제한 : 512MB | 기출 : 삼성전자 SW 역량테스트
문제
- 바이러스의 확산을 막기 위해 연구소에 벽을 세우려 한다.
- 연구소는 N x M인 직사각형이다.
- 연구소는 빈칸, 벽으로 이루어져 있다.
- 일부 칸엔 바이러스가 존재하고 이 바이러스는 상하좌우로 인접한 빈칸으로 확산될 수 있다.
- 새로 세울 수 있는 벽의 개수는 3개이고 꼭 3개를 세워야 한다.
- 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하라.
입력조건
- 첫째 줄에 N, M이 주어진다. (3<=N,M<=8)
- 둘째 줄부터 N개의 줄에 지도 모양이 주어진다.
- 0은 빈칸, 1은 벽, 2는 바이러스다.
- 2<=2의 개수<=10
- 빈칸의 개수>=3
출력조건
- 첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
입력예시
7 7
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
출력예시
27
아이디어
- 시간 제한이 넉넉하다는 것에 주의하자.
- 그래프의 크기는 최대 8x8이다.
- 64칸에 세 개의 벽을 세우는 경우는 64C3으로 제한 시간 안에 충분히 계산할 수 있다.
- 따라서 벽 세 개를 세우는 모든 경우를 고려한다.
- 세운 벽의 개수를 인자로 받는 재귀 함수 dfs(cnt)를 생성한다.
- 0인 곳에 벽을 세우고 벽을 3개 다 세웠다면
- 바이러스를 확산시킨다.
- virus(x,y)라는 함수를 만들고 바이러스가 있는 위치 (x,y)에서부터 DFS로 바이러스를 확산시키는 함수를 만든다.
- 바이러스가 확산된 후에 안전 영역의 개수를 센다.
- cnt_score()라는 함수를 만들고 안전 영역의 개수를 리턴하도록 한다.
- 기존 안전 영역의 개수보다 크다면 그것으로 갱신한다.
- result = max(result, cnt_score())
코드
n,m = map(int,input().split())
graph = []
temp = [[0]*m for _ in range(n)]
result = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for _ in range(m):
graph.append(list(map(int,input().split())))
# 바이러스를 확산시키는 함수
def virus(x,y):
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if 0<=nx<n and 0<=ny<m:
if temp[nx][ny]==0:
temp[nx][ny]=2
virus(nx,ny)
# 안전 영역의 개수를 세는 함수
def cnt_score():
score = 0
for i in range(n):
for j in range(m):
if temp[i][j]==0:
score +=1
return score
def dfs(cnt):
global result
# 세 개의 벽을 다 세웠다면
if cnt==3:
# 바이러스를 확산시키고 그 안전영역을 세기 위해서
# temp 라는 리스트에 graph의 내용을 옮겨담는다
for i in range(n):
for j in range(m):
temp[i][j] = graph[i][j]
# 바이러스를 확산시킨다
for i in range(n):
for j in range(m):
if temp[i][j]==2:
virus(i,j)
# 안전영역의 개수를 갱신한다
result = max(result, cnt_score())
return
# 세 개의 벽을 세우는 모든 경우를 구한다
for i in range(n):
for j in range(m):
if graph[i][j]==0:
graph[i][j]=1
cnt +=1
dfs(cnt)
graph[i][j]=0
cnt -=1
dfs(0)
print(result)
후기
- 벽을 세우는 모든 경우를 다 고려해본다는 생각을 하지 못했다.
- 0이나 1, 2를 기준으로 BFS를 할 수 있는 조건을 찾아보려고 했지만 찾지 못해서 결국 풀이를 참고했다.
- dfs 함수에 어느 기능까지 넣어야 하는지 생각하는 게 어려웠다.