[코드트리 챌린지] 1주차 - 방화벽 설치하기 🥇4

 

방화벽 설치하기

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

⭕ CODE

from collections import deque
from itertools import combinations

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def bfs(x,y):
    q = deque()
    q.append((x,y))
    visited[x][y] = 1
    # 0의 개수 세기위한 count
    count = 0
    # 인접한 곳에 불이 있는지 체크하는 flag
    flag = 0
    while q:
        x,y = q.popleft()
        # 0인 부분 1개 추가
        count += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
            	# 빈공간이고 방문한적이 없다면
                if arr[nx][ny] == 0 and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    q.append((nx,ny))
                # 바로 옆이 불이라면
                # 안전하지 못한 공간 
                if arr[nx][ny] == 2:
                    flag = 1
    return count, flag

n, m = map(int, input().split())

arr = [list(map(int, input().split())) for _ in range(n)]

# 방화벽 가능한 곳 다 담기
li = []
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:
            li.append((i,j))

# 결과값 result
result = 0

# 만약 빈칸이 무조건 3개 이상이 아니라면(여기서는 조건상 3개 이상이다)
# len(li)가 0,1,2인 경우도 나누어서 해결해야한다.

# 방화벽 3개 세우는 모든 경우
comb = list(combinations(li,3))


for i in comb:
    # 가능한 위치에 방화벽을 세움
    arr[i[0][0]][i[0][1]] = 1
    arr[i[1][0]][i[1][1]] = 1
    arr[i[2][0]][i[2][1]] = 1

    visited = [[0] * m for _ in range(n)]

    # 불이 퍼지지 않은 영역 개수
    safe = 0

    for a in range(n):
        for b in range(m):
            # 빈공간이고 방문한적이 없다면
            if arr[a][b] == 0 and visited[a][b] == 0:
                # count : 0의 개수
                # flag : 1이면 불과 인접 0이면 불과 떨어져있다.
                count, flag = bfs(a, b)
                # 주변에 불이 없다면
                if flag != 1:
                    # 불이 퍼지지 않은 영역 개수에 더해준다.
                    safe += count
    # 더 큰값으로 갱신
    result = max(result, safe)

    arr[i[0][0]][i[0][1]] = 0
    arr[i[1][0]][i[1][1]] = 0
    arr[i[2][0]][i[2][1]] = 0
print(result)

 

✏️ Comment

처음에는 불을 막아야 한다고 생각하고 불 근처와 방화벽 근처에만 방화벽을 추가로 만들어야 한다고 생각했다. 그러나

8 6
0 0 0 0 0 0 
0 0 0 0 0 0 
0 1 0 1 0 0 
0 0 0 1 0 0 
2 0 0 0 0 0 
2 0 1 2 2 0 
0 0 0 1 0 0 
0 0 0 1 0 0

 

이 경우에 아래와 같이 방화벽을 세워야 결과값 6이 나왔다.

8 6
0 0 0 1 0 0 
0 0 1 0 0 0 
0 1 0 1 0 0 
1 0 0 1 0 0 
2 0 0 0 0 0 
2 0 1 2 2 0 
0 0 0 1 0 0 
0 0 0 1 0 0​

그래서 방화벽을 세울 수 있는(0의 위치)에 대해서 조합을 사용해서 모든 경우를 탐색하였고 각각의 경우에 가능한 공간을 큰 값으로 바꿔가며 해결해주었다.