[백준] 14502 파이썬(python) : 연구소 - (★)

14502번 : 연구소

 

 

빈칸에 벽을 3개 세워서 바이러스를 퍼지게 한 다음 가장 많은 빈칸이 남도록 해야한다.

1) 빈칸을 돌며 벽 3개를 세운다 -> n, m의 최댓값은 8이기 때문에 완전탐색으로 모든경우를 돌 수 있다. 그리고 벽 3개를 세워 나머지는 배제해야 하기에 백트래킹을 떠올린다.

2) 벽을 모두 세운 후 그 경우에 대해 바이러스를 전파시키는데 연결되어 있는 바로 이웃칸으로 전염될 수 있으니까 bfs를 사용한다. 다 전염시키고 나서 빈칸(0)의 개수를 센다.

==> 백트래킹 안에서 bfs를 호출한다.

 

from collections import deque

visit = [[0 for col in range(10)] for row in range(10) ] #1
dx = [ 0, 0, 1, -1 ] #2
dy = [ 1, -1, 0, 0 ]

def bfs(): #3
    global answer

    for x in range(n): 
        for y in range(m):
            visit[x][y] = lab[x][y] #9
            if lab[x][y] == 2:
                q.append([x, y])
    while q:
        x, y = q.popleft()
        visit[x][y] = 1
        for i in range(4):
            if 0 <= x+dx[i] < n and 0 <= y+dy[i] < m and lab[x+dx[i]][y+dy[i]]==0 and visit[x+dx[i]][y+dy[i]]==0:
                q.append([x+dx[i], y+dy[i]])
                visit[x+dx[i]][y+dy[i]] = 1
    cnt = 0
    for x in range(n):
        for y in range(m):
            if lab[x][y]==0 and visit[x][y]==0:
                cnt += 1
    answer=max(answer, cnt)

def backTraking(select): #4
    if select == 3: #5
        bfs()
        return
    for x in range(n):
        for y in range(m):
            if not lab[x][y]: #6
                lab[x][y] = 1 #7
                backTraking(select+1) #8
                lab[x][y] = 0
                
q = deque()
answer = 0
n, m = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(n) ]
backTraking(0)
print(answer)

 

#1 : #9에서 입력받은 값을 복사받고 바이러스를 전파시켜서 최대개수를 확인하기 위한 임시 리스트

#2 : 동서남북 방향, x가 행이고 y가 열이다.

#3 : #5에서 select(여기서는 깊이가 벽의 개수)가 3일때 호출

#6 : 처음에 벽을 세워야 하는데 지나갈 수 있는 공간(lab[x][y] == 0)이면 벽을 하나 세우고 재귀호출

 

문제해결을 위해 백트래킹에 bfs까지 풀어야하는 문제였다. 

 

다른풀이)

import sys
n, m = map(int, sys.stdin.readline().split())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
tmp, res = [ [0]*m for _ in range(n) ], 0 #1
dx = [ 0, 0, -1, 1 ] #2
dy = [ -1, 1, 0, 0 ]

def count(): #3
    cnt = 0
    for i in range(n):
        for j in range(m):
            if tmp[i][j] == 0:
                cnt += 1
    return cnt

def virus(x, y): #4
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and tmp[nx][ny] == 0: #5
            tmp[nx][ny] = 2
            virus(nx, ny)

def backTracking(wall): #6
    global res
    if wall == 3: #7
        for i in range(n):
            for j in range(m):
                tmp[i][j] = graph[i][j] #8
        for i in range(n):
            for j in range(m):
                if tmp[i][j] == 2: #9
                    virus(i, j)
        res = max(res, count()) #10
        return
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0: #11
                graph[i][j] = 1
                backTracking(wall+1) #12
                graph[i][j] = 0
backTracking(0)
print(res)

 

#1 : 임시로 사용할 리스트와 최종 결과를 출력할 변수 선언

#2 : 방향벡터

#3 : 바이러스가 모두 퍼진 후에 남아있는 안전구역의 개수를 세어줄 함수

#4 : 게이트가 3개 설치되었을때 실행할 virus함수

#5 : tmp[nx][ny]가 0일때만 바이러스 확장

#6 : 모든 경우를 가지치기로 필요한 부분만 분리시킬 백트래킹 함수

#7 : 설치된 게이트가 3개일때

#8 : 게이트가 설치된 graph를 tmp로 복사

#9 : 바이러스를 발견하면 virus함수 실행

#10 : count()함수를 실행하고 그 값이 최대값이면 res에 저장

#11 : 0이면 게이트 설치

#12 : 재귀호출