[백준] 14502 연구소 (파이썬/python)

🎈문제

https://www.acmicpc.net/problem/14502

 

🎁알고리즘 및 접근

bfs, 백트래킹

 

1. 벽을 좀 더 효과적으로 세울 수 있는 알고리즘이 있을지 생각해본다.

2 . 없으면 벽을 일일이 세워보며 어디에 세웠을 때 안전 영역이 가장 클지 경우의 수를 따져보아야 한다.

3. 경우의 수를 따질 때는 파이썬 내장함수를 사용하는 법과 백트래킹이 있는데, 조건이 까다로운 경우 백트래킹을 사용한다.

4. 백트래킹을 사용해 빈 영역마다 벽을 세워보며 안전 영역이 얼마나 남는지 bfs()를 돌려본다.

5. bfs를 사용해도 되고, dfs를 사용해도 되지만, bfs를 선호해서 사용했다.

6. bfs 함수 내에서 바이러스를 퍼트리고 동시에 퍼트릴 때마다 cnt += 1 해주며 퍼트린 영역의 개수를 세어준다.

7. bfs를 돌리고 난 뒤(바이러스를 퍼트리고난 뒤)의 안전 영역 = 퍼트리기 전 안전영역(safe_area) - 바이러스가 퍼진 영역(cnt) - 3(벽 3개)

8. bfs를 돌리고 난 뒤의 안전영역을 기존의 값(answer)과 비교하여 가장 넓은 영역의 값을 저장한다.

 

💻코드

# 14502 연구소

from collections import deque

# 벽세우는 함수, 백트래킹
def makeWall(cnt):
    global answer
    if cnt == 3:
        answer = max(answer,bfs())
        return

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                makeWall(cnt+1)
                graph[i][j] = 0

# bfs
def bfs():
    temp = [t[:] for t in graph] # graph 복사
    deq = deque()
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]
    
    for i in range(n):  # 2(바이러스)의 위치 정보 수집
        for j in range(m):
            if temp[i][j] == 2:
                deq.append([i,j])
    
    cnt = 0 # 바이러스가 퍼진 영역의 개수
    while deq:  # bfs돌려서 바이러스 퍼트리면서 퍼트린 면적 계산
        x,y = deq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx > (n-1) or ny < 0 or ny > (m-1):
                continue
            if temp[nx][ny] == 0:
                temp[nx][ny] = 2
                cnt += 1
                deq.append([nx,ny])

    # 남은 safe_area 개수 반환
    return safe_area-cnt-3  # 처음 safe_area의 면적 - 바이러스 퍼진 면적 - 벽 3개

                


# 입력 받기
n,m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]

# 처음 safe_area의 개수
safe_area = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            safe_area += 1

# 벽 세우고 안전 영역 크기 확인하기
answer = 0
makeWall(0)

print(answer)

🎄코드 설명

주석과 위의 설명으로 대체한다.