백준/ Gold 5 문제 , 백준 파이썬 14502, 연구소 [구현, BFS]

백준/ Gold 5 문제 , 백준 파이썬 14502, 연구소 [구현]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
백트래킹과 bfs를 사용하여 푸는 문제

 

 

 

<문제 출처>

 

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

14502번: 연구소

------------------------------------------------------------------------------------------------------------------------------

 

 

 

<규칙> 

 

1. 바이러스는 상하좌우에 있는 0을 자신과 같은 2로 만든다.

2. 퍼진 바이러스도 똑같이 주위에 영향을 미친다.

3. 1로 둘러 싸여 더이상 퍼질 수 없는 경우나 경계선에 닿으면 바이러스 확산을 종료한다.

4. 대각선에 있는 0 에는 영향을 미치지 않는다.

5. 바이러스는  숫자 1로 막힌 부분을 넘어갈 수 없다.

 

 

 

 

* 접근 방법

 

1. 확산시키면서 벽을 세우는 것이 아닌 벽을 세워두고 확산을 시킨다.

 

2. 벽을 세울 수 있는 모든 경우를 확인 해본다. -> 백트래킹 활용

 

 

3. 벽을 3개 세운뒤 바이러스를 퍼트린다. 이때, 원본 배열을 보존시키기 위해 deepcopy 를 사용한다.

 

또한, deqeue를 활용하여, 바이러스를 지속적으로 퍼트린다. 

더이상 바이러스가 퍼지는 것이 불가능하면 종료되게 while 문을 활용.

 

 

 

4. 이후, 바이러스가 다 퍼진 케이스의 안전구역을 구해준다.

 

 

 

5. 2번 과정을 통해 3~4 번을 케이스마다 반복 시킨다.

 

 

 

 

6. 최종적으로 저장된 가장 큰 안전 영역의 크기를 출력시킨다.

 

 

 

 

* 백트래킹 과정이 어렵다면, 백준 문제중 N과 M 문제 시리즈를 풀면서 연습하면 좋다.

 

 

*참고

https://hongcoding.tistory.com/m/130

[백준] 14502 연구소 (Python 파이썬)

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

 

 

 

from collections import deque
import copy

dq=deque()
N,M=map(int,input().split())
place=[]
parallel=[0,0,1,-1]
vertical=[1,-1,0,0]

for i in range(N):
    place.append(list(map(int,input().split())))
    
def wall(cnt):  # 벽 세우기
    # 벽이 다 세워졌을 때
    if cnt==3:
        diffuse()
        return
    
    for i in range(N):
        for j in range(M):
            if place[i][j]!=1 and place[i][j]!=2 and cnt!=3:
                place[i][j]=1
                wall(cnt+1)
                place[i][j]=0    
                
def safe(check):  # 안전구역 체크
    global result
    tmp=0
    for i in check:
        tmp+=i.count(0)
    if tmp > result:
        result=tmp

def diffuse():  # 바이러스 퍼트리기
    check=copy.deepcopy(place)
    # 바이러스 위치 파악
    for i in range(N):
        for j in range(M):
            if check[i][j]==2:
                dq.append([i,j])
    # 바이러스 퍼트리기 시작
    while dq: 
        i,j=dq.popleft()           
        for k in range(4):
            move_x=i+vertical[k]
            move_y=j+parallel[k]
            if 0 <= move_x <N and 0 <= move_y < M:
                if check[move_x][move_y]==0:
                    check[move_x][move_y]=2
                    dq.append([move_x,move_y])
    # 안전구역 체크
    safe(check)
                
result=0     
wall(0)
print(result)