[DFS/BFS] 백준 14502번: 연구소 Gold IV(Python 파이썬)

💡문제 링크

14502번: 연구소

 

 

💡문제 분석 요약

1. 연구실 지도에서 0은 안전영역, 1은 벽, 2는 바이러스

2. 바이러스(2)는 상하좌우로 퍼진다(1을 만나기 전까지 계속 퍼짐)

3. 벽(1)을 3개 세워서 바이러스의 확산을 최대한 막야아 한다. 즉, 안전영역이 최대가 되어야 한다.

4. 안전영역 최댓값 출력

 

💡알고리즘 설계

1. n, m, 지도를 입력받는다. 지도를 이중 리스트로 받는다.

2. DFS(깊이 우선 탐색)를 이용해서 바이러스를 상하좌우로 전파시키는 virus 함수를 만든다

3. 안전 영역을 계산하는 safe 함수를 만든다

4. DFS(깊이 우선 탐색)를 이용해서 울타리를 설치하면서 매번 안전 영역의 크기를 계산하는 dfs 함수를 만든다

virus(x, y) 함수

- 바이러스의 위치(x, y)에 대하여 상하좌우로 전파

- 재귀해서 최대한 멀리까지 전파

safe() 함수

- temp[i][j]가 0이면 count가 1만큼 증가

- 계산된 count값을 출력

dfs(fence) 함수

- fence는 울타리의 개수

- 비어있는 공간에 울타리를 설치

- 재귀해서 계속 울타리를 설치

- 울타리의 개수가 3이 되었을 때, 각 바이러스의 위치에서 전파 진행하고, 안전 영역 크기 계산

- 이번에 계산한 안전 영역 크기가 이전 안전 영역 크기보다 크면, 안전 영역 크기 갱신

💡코드

n, m = map(int, input().split())
lab = [] # 초기 지도
for _ in range(n):
    lab.append(list(map(int, input().split())))
temp = [[0] * m for _ in range(n)] # 벽 설치한 지도

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

result = 0

# DFS(깊이우선탐색)를 통해 바이러스 전파
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:
                temp[nx][ny] == 2
                virus(nx, ny)
# 안전 영역 크기 계산
def safe():
    count = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                count += 1
    return count

# 울타리를 설치하면서 매번 안전 영역의 크기 계산
def dfs(fence):
    global fence
    # 빈 공간에 울타리 설치
    for i in range(n):
        for j in range(m):
            if lab[i][j] == 0: # lab에서 빈 공간이면 울타리 설치하고, 울타리 개수 1만큼 증가
                lab[i][j] = 1
                fence += 1
                dfs(fence)
                lab[i][j] = 0
                fence -= 1
    # 울타리가 3개 설치된 경우
    if fence == 3:
        # 울타리 3개를 설치한 모습을 temp에 담는다
        for i in range(n):
            for j in range(m):
                temp[i][j] = lab[i][j] 
        # temp에서 바이러스 전파 진행
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i, j)
        # 안전영역의 최댓값 계산
        result = max(result, safe())
        
dfs(0)
print(result)

 

💡 오답 풀이

 

 

💡 다른 풀이

...

 

💡 느낀점 or 기억할정보

어려워서 책 풀이 봤다..