[파이썬(python)] 백준 연구소 14502 dfs bfs

음... 내 코드의 문제가 뭘까. 

bfs 함수를 호출하면 count값만 리턴하고, 배열은 그대로 두어야하는데....

배열도 바꿔서 저장이 된다.

왜지..? 지역변수이기 때문에 함수를 호출할 때마다 배열에 저장된 값은 사라지는게 아닌가?

고민이 필요하다.

 

from collections import deque

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

def bfs(mapp):
    count = 0
    x = mapp

    q = deque()
    for i in range(n):
        for j in range(m):
            if x[i][j] == 2:
                q.append([i,j])

    while q:
        i,j = q.popleft()
        x[i][j] = 2

        if i + 1 < n:
            if x[i+1][j] == 0:
                q.append([i+1, j])

        if j + 1 < m:
            if x[i][j+1] == 0:
                q.append([i, j+1])

        if i - 1 >= 0:
            if x[i-1][j] == 0:
                q.append([i-1, j])
        if j - 1 >= 0:
            if x[i][j-1] == 0:
                q.append([i, j-1])

    for i in range(n):
        for j in range(m):
            if x[i][j] == 0:
                count += 1
            
    
    return count #안전 지대 개수


mapp = []

for _ in range(n):
    mapp.append(list(map(int, input().split())))


build = 0
safe = 0
tmp = 0


for i in range(n):
    for j in range(m):
        if build == 3:
            break
        
        if mapp[i][j] == 0:
            #일단 세워봄
            build += 1
            mapp[i][j] = 1

            tmp = bfs(mapp)
            print(tmp)

            if safe < tmp:
                #안전지대 개수가 늘면 설치 유지
                safe = tmp
                print(safe)
                continue

            #아닐 경우 다시 삭제
            mapp[i][j] = 0
            build -= 1

print(safe)

 

 

 

다시 수정한 코드

 

위 코드의 경우 벽을 하나 설치해본 다음 안전지대개수가 늘지않으면 다시 삭제하는 문제가 있다.

그런데 이 문제는 벽을 총 세개 설치해야해서, 하나씩 설치해본 다음 삭제하는 경우에는 문제에서 요구하는 답을 구할수 없다. 

그리고 함수로 배열을 인자로 넘겨주는 경우, C 처럼 배열의 레퍼런스를 넘겨주는 것이 된다.... 배열값이 변해버림.

따라서 deepcopy를 이용해 함수 안에서 넘겨받은 배열의 값을 복사해야한다.

 

from collections import deque
from itertools import combinations
import sys
import copy

n, m = map(int, sys.stdin.readline().rstrip().split())

#상하좌우
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def virus(loc):
    #loc값이 변하는 것을 피하기 위해
    real_loc = copy.deepcopy(loc)
    
    q = deque()

    for i in range(n):
        for j in range(m):
            if real_loc[i][j] == 2:
                q.append([i, j])
                while q:
                    x, y = q.popleft()

                    for d in range(4):
                        x += dx[d]
                        y += dy[d]

                        if 0 <= x < n and 0 <= y < m:
                            if real_loc[x][y] == 0:
                                real_loc[x][y] = 2
                                q.append([x, y])

                        x -= dx[d]
                        y -= dy[d]

    count = 0
    for i in range(n):
        for j in range(m):
            if real_loc[i][j] == 0:
                count += 1


    return count

loc = []
#연구소 정보 입력받기

for _ in range(n):
    loc.append(list(map(int, sys.stdin.readline().rstrip().split())))

#안전지대 개수
safe = virus(loc)


index = []
#0인 연구소의 인덱스를 저장

for i in range(n):
    for j in range(m):
        if loc[i][j] == 0:
            index.append([i, j])
            

#연구소 3개 선택해서 벽을 세워보기
for x, y, z in combinations(index, 3):
    loc[x[0]][x[1]] = 1
    loc[y[0]][y[1]] = 1
    loc[z[0]][z[1]] = 1

    safe = max(safe, virus(loc))

    #연구소 다시 0으로 저장
    loc[x[0]][x[1]] = 0
    loc[y[0]][y[1]] = 0
    loc[z[0]][z[1]] = 0

print(safe)