[CodeTree/파이썬] 방화벽 설치하기 문제풀이/시간복잡도 줄이기

https://www.codetree.ai/training-field/frequent-problems/problems/firewall-installation/description?page=3&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

사고흐름

1. 방화벽 설치하는 모든 경우 탐색 -> 조합

2. 해당 방화벽 위치에 따른 불 영역 구하기 -> DFS, BFS

 

 

시간 복잡도 줄이기 과정

 

1. 첫번째 시도는 그냥 막 작성한거 -> 시간 초과

2. 처음에는 BFS로 불영역 구할때 for문으로 2인거 찾아서 해당 좌표에서 BFS 시작했는데, 그걸 줄이기 위해 불 영역을 저장한 리스트를 가지고 거기서 차례대로 탐색 -> 2000ms

3. 방화벽 조합 구하는 방법 수정: 원래는 DFS로 구했는데 3중 for문으로 구해봄 (이게 가능했던 것은 3가지만 고르면 되기때문) -> 465ms

4. deque 사용 뺌 -> 580ms

 

두번째코드

n,m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
wall_num = 0
ground = []
comb = []
moves = [(1,0),(0,1),(-1,0),(0,-1)]
fire = []

for i in range(n):
    for j in range(m):
        if board[i][j]==1:
            wall_num+=1
        elif board[i][j]==0:
            ground.append((i,j))
        else:
            fire.append((i,j))

# 방화벽 3개 모든 조합 구하기 
def combination(v):

    if len(v)==3:
        comb.append(v[:])
        return

    for g in ground:
        if g not in v:
            v.append(g)
            combination(v)
            v.pop()

# 불 번짐 
def fire_area(x, y, board):

    q = [(x,y)]
    cnt = 1
    board[x][y]=-1
    while q:
        v = q.pop(0)
        for move in moves:
            dx,dy = v[0]+move[0],v[1]+move[1]
            if 0<=dx<n and 0<=dy<m and board[dx][dy]!=1 and board[dx][dy]!=-1:
                board[dx][dy]=-1
                cnt+=1
                q.append((dx,dy))
    
    return cnt

combination([])
ans = n*m

for com in comb:
    board_copy = [b[:] for b in board]
    fire_cnt = 0
    for c in com:
        board_copy[c[0]][c[1]]=1
    for f in fire:
        if board_copy[f[0]][f[1]]!=-1:
            fire_cnt += fire_area(f[0], f[1], board_copy)
    ans = min(ans, fire_cnt)
print(n*m-ans-wall_num-3)

 

세번째 코드 (최적)

from collections import deque

n,m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
wall_num = 0
ground = []
comb = []
moves = [(1,0),(0,1),(-1,0),(0,-1)]
fire = []

for i in range(n):
    for j in range(m):
        if board[i][j]==1:
            wall_num+=1
        elif board[i][j]==0:
            ground.append((i,j))
        else:
            fire.append((i,j))

# 방화벽 3개 모든 조합 구하기 
def combination():

    for i in range(len(ground)-2):
        for j in range(i+1, len(ground)-1):
            for k in range(j+1, len(ground)):
                comb.append((ground[i],ground[j],ground[k]))

# 불 번짐 
def fire_area(x, y, board):

    q = deque()
    q.append((x,y))
    cnt = 1
    board[x][y]=-1

    while q:
        v = q.popleft()
        for move in moves:
            dx,dy = v[0]+move[0],v[1]+move[1]
            if 0<=dx<n and 0<=dy<m and board[dx][dy]!=1 and board[dx][dy]!=-1:
                board[dx][dy]=-1
                cnt+=1
                q.append((dx,dy))
    
    return cnt

combination()
ans = n*m

for com in comb:
    board_copy = [b[:] for b in board]
    fire_cnt = 0
    for c in com:
        board_copy[c[0]][c[1]]=1
    for f in fire:
        if board_copy[f[0]][f[1]]!=-1:
            fire_cnt += fire_area(f[0], f[1], board_copy)
    ans = min(ans, fire_cnt)
print(n*m-ans-wall_num-3)

 

 

시간 줄이기 팁

1. 조합이나 순열 구할때 DFS나 BFS도 좋지만, comb(n, list) 중 n이 4이하라면 차라리 다중 for문으로 구현하는게 훨 빠를수있다!!

2. deque 사용