[DFS] 연구소

출처 : 이코테
벽(1)을 3개 설치해서 번지는 바이러스(2)를 막아 0의 최대 갯수를 구하라

#input 
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

📍 필요한 것

1. 상하좌우 방향 리스트

2. 바이러스 퍼지게 하는 def virus()

3. 0의 갯수 세는 def get_score()

4. 벽 설치 + 0 갯수 세는 def dfs()

n, m = map(int, input().split())
data = []
temp = [[0] * m for _ in range(n)]
print(temp)

for _ in range(n):
  data.append(list(map(int,input().split())))
print(data)
#[[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]]
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 nx < n and ny >= 0 and ny < m:
      if temp[nx][ny] == 0: # 범위 안이고 0이라면 
        temp[nx][ny] = 2 # #원본 데이터 대신 temp 사용
        virus(nx,ny) # 재귀 

def get_score(): # 안전 영역(0개수) 
  score = 0
  for i in range(n):
    for j in range(m):
      if temp[i][j] == 0: # 변해야 하는 temp 사용
        score += 1
  return score


def dfs(count): # 벽 설치 
  global result

  if count == 3: # 벽 3개
    for i in range(n):
      for j in range(m):
        temp[i][j] = data[i][j] # 원본을 temp로 다 저장 

    for i in range(n):
      for j in range(m):
        if temp[i][j] == 2: # 바이러스라면
          virus(i,j) # 퍼지게해라

    # 0의 갯수의 최대값 
    print("temp",temp)
    result = max(result, get_score())
    return 

# --------------------분기 
  for i in range(n): # 벽 설치가 3개 미만이면 
    for j in range(m):
      if data[i][j] == 0: # 0이라면 벽 설치해라
        data[i][j] = 1
        count += 1 # 벽 갯수 + 1
        dfs(count)
        data[i][j] = 0 # 원본 되돌리기 
        count -= 1
        # for문으로 [0][0], [0][1], [1][0] 반복
dfs(0)
print(result)

tmp의 역할

temp는 초기 맵의 상태를 보존하기 위한 역할을 합니다. 주어진 코드에서 temp는 미로의 현재 상태를 저장하고, 벽을 설치하고 바이러스를 퍼뜨린 후에도 이전 상태를 유지하는 데 사용됩니다.
미로 상태를 temp에 복사하는 이유는 다음과 같습니다:
1. dfs 함수에서 벽을 설치하고 시뮬레이션을 진행할 때, 원본 data 맵을 변경하게 되면, 한 번의 시뮬레이션이 끝난 후에 이전 상태로 돌리기가 어려워집니다.
2. 따라서 temp라는 복사본을 만들어 현재 상태를 저장하고, 이를 활용하여 벽을 설치하고 바이러스를 퍼뜨린 다음에도 temp를 원상태로 복원하여 다음 시뮬레이션에 활용합니다.
3. 이러한 방식으로 dfs 함수가 벽을 설치하는 과정을 시뮬레이션할 때, data 맵을 변경하지 않고 temp를 사용하여 상태를 조작하므로, 시뮬레이션 간의 상태 공유 및 초기화가 편리하게 이루어집니다.
요약하면, temp는 맵의 현재 상태를 보존하고 시뮬레이션을 수행하는 동안에만 변경되는 맵으로 사용됩니다. 이를 통해 원본 데이터(data)를 손상시키지 않으면서 다양한 시뮬레이션을 수행할 수 있게 됩니다.