[백준] 14502번 연구소 파이썬

NxM 크기 연구소.

바이러스는 상하좌우 인접한 빈 칸으로 퍼짐

새로 세울 수 있는 벽의 개수는 3개

0 == 빈 칸, 1 == 벽, 2 == 바이러스

안전 영역의 크기의 최댓값을 구하자.

 

- 입력

1줄 : N, M

 

- 출력

2~N줄 : 지도의 모양(0 == 빈 칸, 1 == 벽, 2 == 바이러스)

 

고민) 2의 위치를 먼저 찾아두고 확산을 고려해야 하나? 아니면 전체 center에서 돌면서 2가 나왔을 때에 상하좌우를 고려해야 하나? 후자의 방법으로 구현하려고 했으나.. 그럼 3개의 벽을 먼저 만들고서 값을 계산해야 할까? 

n, m = map(int, input().split())

center = list([map(int, input.split())] for _ in range(n))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

#0은 빈 칸, 1은 벽, 2는 바이러스
nx, ny = 0, 0
for i in range(4):
  nx = nx + dx[i]
  ny = ny + dy[i]

  if 0 > nx >= m or 0 > ny >= m:
    continue

  if center[nx][ny] == 1:
    #?
  if center[nx][ny] == 2:
    

cnt = 0
for i in range(n):
  for j in range(m):
    if center[i][j] == 0:
      cnt += 1
    else:
      continue
print(Cnt)

 

14502번 연구소

해답) graph에서 값이 0이면 벽을 세울 수 있는데 무조건 3개의 벽을 세운 후에 바이러스를 확산시킨다. dfs()함수에 처음 count를 0으로 넣어준다. 아직 벽을 세우기 전이니까! 해당 count가 3이 되기 전이므로 0으로 된 곳에 벽을 설치하여 1을 대입한다. 그리고 카운트를 증가시켜주고 dfs함수를 재귀호출한다. 이를 통해 dfs(0) -> dfs(1) -> dfs(2) -> dfs(3)을 호출하게 되고 count가 3이 되었을 때는 graph를 temp에 복사해두고 temp에 있는 바이러스 2를 virus함수를 사용해 확산시킨다. virus함수에서는 해당 좌표를 받았으니 dx, dy와 함께 상하좌우 이동을 하게 되고 칸이 0이라면 2로 바꿔준다. 확산이 완료되면 result를 얻기 위해서 score함수를 호출하는데 해당 함수는 temp에 있는 0의 개수를 세어서 최종적으로 여러 벽 조합들 중에서 안전한 공간의 개수가 가장 많은 경우의 값을 찾아준다. => dfs를 재귀로 호출하고나서 다시 graph의 해당 좌표를 0으로 초기화하고 count도 -1해서 처음으로 복구시켜주어야한다. 이를 통해 벽 3개의 모든 조합들을 구현할 수 있음이다...!

import sys
n,m =  map(int,sys.stdin.readline().split())
graph = []
temp = [[0]*m for _ in range(n)]
for _ in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))

dx = [-1,0,1,0]
dy = [0,-1,0,1]

result = 0
#바이러스를 퍼지게 하는 함수
def virus(x,y):
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if nx>=0 and ny>=0 and nx<n and ny<m:
            if temp[nx][ny]==0:
                temp[nx][ny] = 2
                virus(nx,ny)
#현재맵에서 안전영역 크기 계산 메서드
def score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score+=1
    return score


#깊이 우선 탐색(DFS를 이용해 울타리를 설치하면서 안전영역의 크기를 계산)
#count : 울타리 갯수
def dfs(count):
    global result
    if count == 3:
        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,score())
        return

    #빈공간에 울타리 설치 
    #DFS 이용해 울타리 설치 가능한 모든경우의 수 탐색
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                count+=1
                dfs(count)
                graph[i][j] = 0
                count-=1
                #맵의 상태가  count값이 3이 된 이전과 이후가 계속해서 바뀌기 때문에 
                #모든 울타리 설치 경우의 수를 구할 수 있다.
dfs(0)
print(result)

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

14502번: 연구소

참고 : https://hae-sooo97.tistory.com/31

[백준-14502번-연구소] - 파이썬