[백준] 17142 - 연구소 3 [Python(파이썬)]

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

1. 문제

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

2. 풀이

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

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

3. 코드

from collections import deque
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
selceted = [False] * 10
dx , dy = [1, -1, 0, 0], [0, 0, 1, -1]
que, virus, vacnt, ret = deque(), [], 0, float('inf')

def solution():
    global virus, vacnt, ret
    # 바이러스 전파
    def bfs(chk):
        global ret
        infect, times = 0, 0
        while que:
            x, y = que.popleft()
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if nx < 0 or nx >= N or ny < 0 or ny >= N:
                    continue
                if board[nx][ny] != 1 and chk[nx][ny] == -1: #벽이 아니고 처음 들렸을 때
                    chk[nx][ny] = chk[x][y] + 1
                    que.append((nx,ny))
                    if board[nx][ny] == 0:
                        infect += 1
                        times = chk[nx][ny]
        if infect == vacnt:
            ret = min(ret, times)

    # 바이러스 M개 선택
    def solve(idx, cnt, v): 
        global que
        if cnt == M:
            chk = [[-1] * N for _ in range(N)]
            for i in range(v):
                if selceted[i]:
                    x, y = virus[i]
                    que.append((x, y))
                    chk[x][y] = 0
            bfs(chk)
            return
        for i in range(idx, v):
            if not selceted[i]:
                selceted[i] = True
                solve(i+1, cnt+1, v)
                selceted[i] = False

    # 초기 빈칸의 개수와 바이러스 위치 저장
    for i in range(N):
        for j in range(N):
            if board[i][j] == 2:
                virus.append([i,j])
            elif board[i][j] == 0:
                vacnt += 1

    solve(0,0,len(virus))

    if ret == float('inf'):
        return -1
    return ret     
print(solution())

• 결과 : 896 ms
• 연구소 1,2 문제를 풀고 다시 풀어보니 정리가 된 느낌이다... 다들 한번 풀어보면 좋을거 같다.

---

References

•  

---

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