[백준 / 파이썬(Python3) / #14502 ] 연구소

문제 출처 https://www.acmicpc.net/problem/14502

14502번: 연구소

문제 설명

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

 

요약

연구소 NxM 크기에 빈 칸(0), 벽(1), 바이러스(2) 가 있다.

바이러스(2)는 상, 하, 좌, 우의 빈 칸(0)으로 퍼질진다.

새로 세울 수 있는 벽은 3개로 고정된다.

벽을 3개 세운 뒤 바이러스가 퍼지지 않은 안전구역(빈 칸)의 최대 개수를 출력해야 한다.

 

삼성 SW역량 테스트 기출문제였다고 합니다.

이 문제를 풀려면

1. 조합

2. 너비우선탐색(Breadth First Search) 또는 깊이우선탐색(Depth First Search)

개념을 이해하고 구현할 줄 알아야 합니다.

 

● 어떻게 풀까

1. 벽을 3개 세우고 → 조합 사용

2. 바이러스를 퍼뜨리고 →BFS 또는 DFS 사용

3. 안전구역의 수를 세고

4. 그 중 최대값을 출력하면 됨

 

● 풀이

1. 입력값을 받아서 변수로 지정하기

프로그래머스에서는 입력값이 자동으로 처리되는데

백준에서는 문제의 입력값을 직접 받아서 처리하는 코드를 넣어야 문제를 풀 수 있습니다.

import copy   #추후에 배열을 복사하기 위해 copy모듈 삽입
import sys    #입력모듈 사용 위함

input = sys.stdin.readline

#첫 줄에 들어오는 지도의 세로N, 가로M을 입력받기
n, m = map(int, input().strip().split())

#지도의 세로N과 가로M을 배열화하기
nm = [list(map(int, input().split())) for _ in range(n)]

 

2. 편리한 작업을 위한 처리 

3개의 벽을 선택하기에 앞서, 바이러스가 전파되는 방향을 미리 리스트로 만들어줍니다.

최종적으로 안전구역의 개수를 return할 것이기 때문에, 안전구역의 개수를 return 하기 위한 변수도 미리 생성합니다.

그리고 바이러스의 위치를 파악하는 리스트를 만듭니다.

#상하 단위로 이동
direct_a = [-1,0,1,0]

#좌우 단위로 이동
direct_b = [0,1,0,1]

#안전구역의 개수를 return 하기 위한 변수
max_safe = 0

#바이러스의 위치 리스트 만들기
for i in range(N):
    for j in range(M):
        if NM[i][j] == 2:              #위치값이 바이러스(2)이면
            virus_list.append([i, j])  #리스트에 추가

 

3. 벽 선택하기

벽을 선택하는 함수를 만들어줍니다.

 

3 - (1)

벽이 3개라면 문제의 요구조건을 만족하기 때문에 주어진 바이러스 개수만큼 주변에 바이러스를 퍼뜨리러 가는 함수spread_virus를 호출합니다.

def select_wall(start, count):
    global max_safe
    if count == 3:  # 종료조건. 벽 3개 선택
        sel_nm = copy.deepcopy(nm)  #벽이 선택된 배열 복사
        for num in range(len(virus_list)):
            a, b = virus_list[num]
            spread_virus(a, b, sel_nm)
        safe_counts = sum(i.count(0) for i in sel_nm)  #안전구역 세기
        max_safe = max(max_safe, safe_counts)
        return True

 

3 - (2)

벽이 3개가 아니라면, 바이러스가 아니면서 벽이 아닌 구역(안전영역-0)에 벽을 만들 수 있습니다.

주어진 지도에서 a, b 좌표로 벽을 세워보려면 2차원 배열에서 a, b의 조합을 뽑아야 합니다.

#2차원 배열에서 a, b 의 좌표를 구하는 방법
start = 0
n, m = 2, 3
for i in range(start, n*m):
    a = i//m
    b = int(i%m)
    print(a, b)

print의 결과는

0 0

0 1

0 2

1 0

1 1

1 2

입니다.

 

2행 3열에서 나올 수 있는 (a, b) 좌표의 모든 조합을 나타내고 있군요!

 

(a, b) 좌표의 모든 조합을 구한 뒤 해당 좌표의 상태가 벽인지, 바이러스인지, 안전구역인지 판단합니다.

안전구역이라면 벽으로 바꿔주면 되겠네요.

 

select_wall()을 재귀적으로 호출합니다. 호출이 끝나면 세운 벽을 다시 빈 칸(0)으로 초기화합니다.

    else:
        for i in range(start, n*m):
            a = i // m
            b = i % m
            if NM[a][b] == 0:  # 안전영역인 경우 벽으로 선택가능
                NM[a][b] = 1  # 벽으로 변경
                select_wall(i, count + 1)  # 벽 선택
                NM[a][b] = 0  #위에 세운 벽을 다시 빈 칸(0)으로 만든다 - 초기화

 

3 - (1)단계와 3 - (2)단계를 합친 3단계의 최종 코드문입니다.↓

def select_wall(start, count):
    global max_safe
    if count == 3:  # 종료조건. 벽 3개 선택
        sel_nm = copy.deepcopy(nm)  #벽이 선택된 배열 복사
        for num in range(len(virus_list)):
            a, b = virus_list[num]
            spread_virus(a, b, sel_nm)
        safe_counts = sum(i.count(0) for i in sel_nm)  #안전구역 세기
        max_safe = max(max_safe, safe_counts)
        return True
    else:
        for i in range(start, n*m):
            a = i // m
            b = i % m
            if NM[a][b] == 0:  # 안전영역인 경우 벽으로 선택가능
                NM[a][b] = 1  # 벽으로 변경
                select_wall(i, count + 1)  # 벽 선택
                NM[a][b] = 0  #위에 세운 벽을 다시 빈 칸(0)으로 만든다 - 초기화

 

4. 바이러스 퍼뜨리기

바이러스를 퍼뜨리는 함수를 만듭니다.

먼저 sel_nm 리스트에서 좌표 (a, b)가 바이러스라면

상하좌우 4방향을 확인하고 연구실 지도의 범위(NxM)를 벗어나지 않는다면 바이러스를 퍼뜨려주는 재귀호출을 이용합니다.

def spread_virus(a, b, sel_NM):
    if sel_NM[a][b] == 2:
# 상하좌우 4방향을 확인하고 범위를 벗어나거나, 벽을만날때까지 반복
        for direct in range(4):
            next_a = a + direct_a[direct]
            next_b = b + direct_b[direct]
            if next_a >= 0 and next_b >= 0 and next_a < N and next_b < M:  
            # 범위를 벗어나지 않을때
                if sel_NM[next_a][next_b] == 0:
                    sel_NM[next_a][next_b] = 2
                    spread_virus(next_a, next_b, sel_NM)

 

● 최종 코드

import copy
import sys

input = sys.stdin.readline

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

direct_a = [-1, 0, 1, 0]  # 위아래 row 단위로 이동
direct_b = [0, 1, 0, -1]  # 좌우 column 단위로 이동
max_safe = 0  # 안전구역의 개수를 return 하기 위한 변수
virus_list = []  # 바이러스 리스트 만들기
for i in range(N):
    for j in range(M):
        if nm[i][j] == 2:
            virus_list.append([i, j])


# 벽 선택하기
def select_wall(start, count):
    global max_safe
    if count == 3:  # 종료조건, 벽 3개 선택 완료
        sel_nm = copy.deepcopy(nm)  # deepcopy로 벽이 선택된 배열 복사
        for num in range(len(virus_list)):
            a, b = virus_list[num]
            spread_virus(a, b, sel_nm)
        safe_counts = sum(i.count(0) for i in sel_nm)  # clean 지역 count
        max_safe = max(max_safe, safe_counts)
        return True
    else:
        for i in range(start, n * m):  # 2차원 배열에서 조합 구하기
            a = i // m
            b = i % m
            if nm[a][b] == 0:  # 안전영역인 경우 벽으로 선택가능
                nm[a][b] = 1  # 벽으로 변경
                select_wall(i, count + 1)  # 벽선택
                nm[a][b] = 0




def spread_virus(a, b, sel_nm):
    if sel_nm[a][b] == 2:
        # 상하좌우 4방향을 확인하고 범위를 벗어나거나, 벽을만날때까지 반복
        for direct in range(4):
            next_a = a + direct_a[direct]
            next_b = b + direct_b[direct]
            if next_a >= 0 and next_b >= 0 and next_a < n and next_b < m:  # 범위를 벗어나지 않을때
                if sel_nm[next_a][next_b] == 0:
                    sel_nm[next_a][next_b] = 2
                    spread_virus(next_a, next_b, sel_nm)


select_wall(0, 0)
print(max_safe)

 

 

다른 사람의 풀이는 7/9 이후 업로드 예정