[n14502] 연구소 in python

 

너무 어렵다 ㅠㅠ  어려어ㅜ...

 

혼자 끙끙 고민하다가

결국 인터넷에서 풀이를 찾아봤다!

 

 

바이러스 퍼지게 하는 건 재귀함수로 하면 될 것 같았지만,

벽을 어디에 세워야할지 정하는 기준을 몰라서 헤맸던 문제

 

 

일단 바이러스가 있는 위치를 리스트로 저장하기

벽 선택하는 함수 1개

바이러스를 퍼트리는 함수 1개를 구현

 

1. 벽 선택하는 함수

벽 count가 3 미만인 경우와 count가 3인 경우를 나눠서 생각해줘야한다.

 

벽 count가 3 미만이라면?

> 벽을 선택하는 과정이 들어가줘야한다.

경우의 수가 많이 없으므로 처음부터 끝까지 for문을 돌린다. (총 횟수 : n*m-start )

현재 위치가 빈 벽이면 벽을 세우고 재귀함수를 호출! 

(그 자리에서부터 다시 벽을 세울 자리를 탐색)

 

재귀함수의 수행이 끝나면

다시 벽을 없앤다.

 

벽 count가 3이라면?

> 이제 바이러스를 퍼트려줄 차례

바이러스가 있던 곳을 중심으로 spread_virus 함수 실행

safe_count를 구할 때 sum과 count를 이용하면 

손쉽게 0의 총 개수를 구할 수 있다! **

( 난 여태까지 count로만 세는 줄 알았는데 아니었다 ㅎ..ㅎ )

 

# 벽 선택하기
def wall(start, cnt):
    global answer
    if cnt == 3:  # 벽 3개 선택시
        # 바이러스 퍼트릴거야!
        current_array = deepcopy(array)
        for r, c in virus: # 바이러스가 있는 곳을 중심으로 spread_virus함수 실행
            spread_virus(r, c, current_array)
        # 안전영역 개수 sum(i.count(0) for i in 배열)!!!!
        safe_count = sum(k.count(0) for k in current_array)
        answer = max(answer, safe_count)
        return

    else:  # 벽 선택하는 과정
        for i in range(start, n * m):  # 2차원 배열을 1차원 배열로 계산하는 방법 : for문 줄이기!!
            r = i // m  # 2차원 배열 행 : i // 열의 수
            c = i % m  # 2차원 배열 열 : i % 열의 수
            # start=0이면, r은 0, c는 0
            # start=2이면, r은 0, c는 2
            if array[r][c] == 0:
                array[r][c] = 1  # 벽 선택 과정
                wall(i, cnt + 1)  # 재귀 함수 돌리기
                array[r][c] = 0  # 벽 해제과정

---

2. 바이러스 퍼트리는 함수!

상하좌우 확인해가면서 범위 안에 있고 0일 경우에만 바이러스로 채운다.

dfs 방식!

# 바이러스 퍼트리기
def spread_virus(r, c, current_array):
    if current_array[r][c] == 2:  # 바이러스라면?
        # 상하좌우 확인
        for i in range(4):
            nx = r + dx[i]
            ny = c + dy[i]
            if 0 <= nx < n and 0 <= ny < m:  # 범위 안에 있을 경우
                if current_array[nx][ny] == 0:  # 빈 벽일 경우
                    current_array[nx][ny] = 2  # 바이러스로 빈 벽을 채운다.
                    spread_virus(nx, ny, current_array)

---

최종 코드

'''
바이러스 > 상하좌우 인접한 빈칸으로 이동 가능
새로 새울 수 있는 벽의 개수는 3개 (꼭 3개 세워야한다)
안전 영역 크기 개수 > 0의 개수
'''
from copy import deepcopy

n, m = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(n)]

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

# 바이러스 리스트를 미리 만들어두기
for i in range(n):
    for j in range(m):
        if array[i][j] == 2:
            virus.append((i, j))


# 벽 선택하기
def wall(start, cnt):
    global answer
    if cnt == 3:  # 벽 3개 선택시
        # 바이러스 퍼트릴거야!
        current_array = deepcopy(array)
        for r, c in virus: # 바이러스가 있는 곳을 중심으로 spread_virus함수 실행
            spread_virus(r, c, current_array)
        # 안전영역 개수 sum(i.count(0) for i in 배열)!!!!
        safe_count = sum(k.count(0) for k in current_array)
        answer = max(answer, safe_count)
        return

    else:  # 벽 선택하는 과정
        for i in range(start, n * m):  # 2차원 배열을 1차원 배열로 계산하는 방법 : for문 줄이기!!
            r = i // m  # 2차원 배열 행 : i // 열의 수
            c = i % m  # 2차원 배열 열 : i % 열의 수
            # start=0이면, r은 0, c는 0
            # start=2이면, r은 0, c는 2
            if array[r][c] == 0:
                array[r][c] = 1  # 벽 선택 과정
                wall(i, cnt + 1)  # 재귀 함수 돌리기
                array[r][c] = 0  # 벽 해제과정


# 바이러스 퍼트리기
def spread_virus(r, c, current_array):
    if current_array[r][c] == 2:  # 바이러스라면?
        # 상하좌우 확인
        for i in range(4):
            nx = r + dx[i]
            ny = c + dy[i]
            if 0 <= nx < n and 0 <= ny < m:  # 범위 안에 있을 경우
                if current_array[nx][ny] == 0:  # 빈 벽일 경우
                    current_array[nx][ny] = 2  # 바이러스로 빈 벽을 채운다.
                    spread_virus(nx, ny, current_array)


wall(0, 0)
print(answer)

---

참고 블로그 링크

https://mentha2.tistory.com/24

[백준] 14502번: 연구소 풀이 with Python