[백준/bfs] 14502번: 연구실/ 다시 푼 것

-문제: https://www.acmicpc.net/problem/14502

14502번: 연구소

참고할만한 다른 풀이 

 

전에 비해서는 이해가 갔다. 

문제를 이해한 내용은 

1. 바이러스의 위치정보 저장(굳이 필요 없었음)

2. 벽 3개를 임의의 위치에 세운다

3. 2 근방에 있는 모든 0을 2로 바꾼다

4. 전체 행렬에서 0의 갯수를 구한다

5. 위 단계를 반복하다가 0의 갯수의 최댓값을 출력한다

이다. 

 

벽 3개를 어떻게 세워야 할지 몰랐는데, 이는 무작위로 0인 지점에 1 3개를 세우고 진행하면 된다.

그 다음 바이러스 주변에 있는 0들을 2로 바꾸어 준다(나는 bfs를 이용했다)

전체 데이터에서 0의 갯수를 구하는 함수를 구현한다 

위 과정을 반복하면서 갯수의 최댓값을 구한후 출력하면 끝 

 

-문제 풀다 헤맸던 것들

: answer=max ,return 라인 들여쓰지 않은 것

if nx,ny 라인도 들여쓰지 않은 것 

pypy3으로 돌리지 않은 것 

q.append(x,y)가 아닌 q.append((x,y))인것 

 

from collections import deque
n,m= map(int,input().split())
data=[]
temp=[[0]*m for _ in range(n)]
answer=0

for i in range(n):
    data.append(list(map(int,input().split())))
dx=[-1,1,0,0]    
dy=[0,0,-1,1]

def virus(x,y):
    q=deque()
    q.append((x,y))
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<= nx <n and 0<=ny<m:
                if temp[nx][ny]==0:
                    temp[nx][ny]=2
                    q.append((nx,ny))
                
def get_num():
    num=0
    for i in range(n):
        for j in range(m):
            if temp[i][j]==0:
                num+=1
    return num

def dfs(count):
    global answer
    if count==3:
        for i in range(n):
            for j in range(m):
                temp[i][j]=data[i][j]
        for i in range(n):
            for j in range(m):
                if temp[i][j]==2:                    
                    virus(i,j)
        answer=max(answer,get_num())
        return 
    for i in range(n):
        for j in range(m):
            if data[i][j]==0:
                data[i][j]=1
                count+=1
                dfs(count)
                data[i][j]=0
                count-=1
dfs(0)
print(answer)