[BOJ] 17142번 연구소3 / 사용언어 : 파이썬(python)

※ 문제링크

17142번: 연구소 3

해당 문제는 DFS, BFS를 활용하여 풀 수 있는 문제였다. 해결하는 방법을 떠올리는 것 어렵지 않았으나, 문제 자체를 잘못 이해하여 코드를 수정하느라 꽤 시간이 걸린 문제였다. 가장 주의해야할 부분은 원래부터 바이러스가 존재하지 않던 경로가 모두 감염된 이후의 비활성 바이러스들을 활성화 시키는 것은 시간을 카운트를 하면 안되고, 경로들이 모두 감염되지 않은 상태에서 바이러스를 활성화하는 상황이라면 시간을 카운트 해주어야 한다는 것이었다. 자세한 문제풀이 방법과 코드는 아래와 같다.

1. 입력값을 2차원 배열형태로 변환해주고, 방문기록을 확인할 2차원 배열을 추가적으로 작성해준다.

2.  완전탐색을 통해 바이러스가 들어갈 수 있는 위치는 좌표값을 저장하고(활성화시킬 조합수를 작성하기 위함)벽의 개수(바이러스가 모두 퍼질 수 있는 확인하는 용도), 바이러스가 없는 경로의 개수를 카운트하여 저장해준다.

3. DFS와 백트래킹을 통해 바이러스가 퍼질 수 있는 조합수를 산출하여 리스트에 저장해준다.

4. 바이러스를 퍼지게 하고 시간을 카운트할 BFS 함수를 작성해준다(비활성 바이러스를 반드시 고려해야함)

5. 예외적인 경우들(초기 배열에 0이 없을 경우, 어떤 경우에도 바이러스를 퍼트릴 수 없을 경우)을 고려해 값을 출력한다.

+ 바이러스가 모두 퍼질 수 있는지에 대한 체크는 바이러스에 감염된 곳의 위치와 벽의 개수를 더해서 구하였다.

+ 시간 및 메모리 단축을 위해 sys함수를 사용하였습니다.

 

# 바이러스가 퍼질 수 있는 위치리스트 생성 및 조합수 확인(dfs)
def check_virus_cd(start):
    if len(virus) == M:
        case.append(virus[:])
        return 
    
    for i in range(start, len(virus_cd)):
        if check[i]:
            continue

        check[i] = True
        virus.append(virus_cd[i])
        check_virus_cd(i)
        virus.pop()
        check[i] = False

def bfs(case_N):
    queue = deque()
    for cs in case_N: # 바이러스 활성화
        queue.append(cs)
        x, y = map(int, cs)
        visited[y][x] = True

    cnt = -1
    virus_cnt = M # 바이러스가 퍼진 개수 확인
    ch_cnt = 0
    while queue:
        cnt += 1
        check_V1 = 0
        check_V2 = len(queue)
        for _ in range(len(queue)):
            x, y = queue.popleft()
            if field[y][x] == 2:
                check_V1 += 1
            if field[y][x] == 0:
                ch_cnt += 1
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < N and 0 <= ny < N:
                    if visited[ny][nx] == False and field[ny][nx] != 1:
                        queue.append([nx, ny])
                        visited[ny][nx] = True
                        virus_cnt += 1
        if check_V1 == check_V2 and ch_cnt == zero: # 경로에 바이러스가 모두 퍼진 상태면 시간 카운트 취소
            cnt -= 1

    return cnt, virus_cnt

import sys
from collections import deque

N, M = map(int, input().split())
field = []
for _ in range(N):
    line = list(map(int, input().split()))
    field.append(line)

virus_cd = []
wall_cnt = 0
zero = 0
for x in range(N):
    for y in range(N):
        if field[y][x] == 2:
            virus_cd.append([x, y])
        if field[y][x] == 1:
            wall_cnt += 1
        if field[y][x] == 0:
            zero += 1


virus = []
check = [False for _ in range(len(virus_cd))]
case = [] # 바이러스를 설치 가능한 위치리스트
check_virus_cd(0)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ans_list =[]
for css in case:
    visited = [[False for _ in range(N)] for _ in range(N)]
    cnt, virus_cnt = bfs(css)
    # 벽의 개수와 감염된 곳의 개수의 합을 배열의 크기와 비교함으로서 바이러스가 모두 퍼질 수 있는지 확인
    if virus_cnt + wall_cnt == N**2: 
        ans_list.append(cnt)

if zero == 0:
    print(0)
elif len(ans_list) == 0:
    print(-1)
else:
    print(min(ans_list))

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.