[백준] 17141 - 연구소 2 [Python(파이썬)]

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀
문제 👉 17141번: 연구소 2

1. 문제

1. N*N 크기의 연구소는 빈 칸과 벽 그리고 M개의 바이러스로 이루어져 있다.
2. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
3. 어떤 바이러스를 놓았을 때, 바이러스가 퍼지는 최소 시간을 출력한다.

2. 풀이

브루트포스와 BFS를 이용한 문제 풀이

1. 브루트포스를 통해 M개의 바이러스를 선택한다.
2. BFS를 통해 바이러스의 전파 최대 시간을 구한다.

3. 코드

from collections import deque
import sys
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
chk, virus, select, ret = [], [], [], sys.maxsize
d = [(-1,0), (1,0), (0,-1), (0,1)]

def solution():
    global arr
    # 바이러스 전파
    def bfs():
        global que, chk, ret
        cnt = 0
        while que:
            x, y = que.popleft()
            for dx, dy in d:
                nx, ny = x+dx, y+dy
                if 0 <= nx < N and 0 <= ny < N and chk[nx][ny] == -1:
                    if arr[nx][ny] == 0:
                        chk[nx][ny] = chk[x][y] + 1
                        cnt = max(cnt, chk[nx][ny])
                        que.append([nx, ny])

        for i in range(N):
            for j in range(N):
                if arr[i][j] == 0 and chk[i][j] == -1:
                    cnt = sys.maxsize
        ret = min(ret, cnt)

    # 바이러스 M개 선택
    def solve(index):
        global select, chk, que, ret
        if len(select) == M:
            chk = [[-1]*N for _ in range(N)]
            que = deque()
            for i,j in select:
                chk[i][j] = 0
                que.append((i,j))
            bfs()
            return
        for idx in range(index, len(virus)):
            i, j = virus[idx]
            if (i,j) not in select:
                select.append((i,j))
                solve(idx+1)
                select.pop()

    # 초기 빈칸과 바이러스 위치 저장
    for i in range(N):
        for j in range(N):
            if arr[i][j] == 1:
                arr[i][j] = '-'
            if arr[i][j] == 2:
                arr[i][j] = 0
                virus.append((i, j))

    solve(0)
    if ret == sys.maxsize:
        print(-1)
    else:
        print(ret)

solution()

• 결과 : 1004 ms

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋