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

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀

문제 👉 14502번: 연구소

1. 문제

1. N*M 크기의 연구소는 빈 칸(0)과 벽(1) 그리고 바이러스(2)로 이루어져있다.
2. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
3. 추가로 3개의 벽을 세워 바이러스가 가장 적게 퍼지게 한다.
4. 안정 영역의 최댓값을 출력한다. -> 바이러스가 최소일 때를 구하는 문제

2. 풀이

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

1. 바이러스의 최솟값을 구한다.
2. 초기 빈 칸의 개수와 바이러스 위치를 저장
3. 브루트포스를 통해 3개의 벽을 세울 수 있는 모든 경우를 고려한다.
4. DFS를 통해 바이러스의 총 개수를 구한다.
5. 안전 영역 = 총 빈칸 - 최소 바이러스 개수 - 벽의 개수(3)

3. 코드

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
chk = [[False]*M for _ in range(N)]
v, zeros, virus = [], 0, 100
d = [(-1,0), (1,0), (0,-1), (0,1)]

def solution():
    global zeros
    # 바이러스 전파
    def dfs(x, y):
        global chk
        res = 1
        chk[x][y] = True # True -> 바이러스 O
        for dx, dy in d:
            nx, ny = x+dx, y+dy
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if not (chk[nx][ny] or arr[nx][ny]): # 바이러스도 아니고 벽도 아닐 때
                res += dfs(nx, ny)
        return res
    # 벽 3개 선택
    def solve(wall, x, y):
        global chk, virus
        if wall == 3:
            cnt = 0
            chk = [[False]*M for _ in range(N)] # False -> 바이러스 X
            for i, j in v:
                cnt += dfs(i, j)
            virus = min(virus, cnt) # 최소 바이러스 개수
            return

        for i in range(x, N):
            k = y if i == x else 0
            for j in range(k, M):
                if arr[i][j] == 0:
                    arr[i][j] = 1
                    solve(wall+1, i, j+1)
                    arr[i][j] = 0

    # 초기 빈칸과 바이러스 위치 저장
    for i in range(N):
        for j in range(M):
            if arr[i][j] != 1:
                zeros += 1
            if arr[i][j] == 2:
                v.append((i, j))

    solve(0, 0, 0)
    print(zeros-virus-3) # 안전 영역 = 빈공간 - 바이러스 - 벽(3) 

solution()

• 결과는 3800 ms 나왔다.

---

References

•  

---

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