[백준] 14502 연구소

문제 설명

• bfs와 재귀를 사용하여 현재 맵의 형태에 벽을 3개 설치했을때 바이러스(2)가 상하좌우로 갈 수 있는 모든 길을 갔을 때 퍼지지 못한 지역(0)의 최대 갯수가 되는 것은 몇개인지 구하는 문제

코드_v1

import copy
import sys


def bfs():
    queue = []
    copied_maps = copy.deepcopy(maps)
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    for i in range(n):
        for j in range(m):
            if copied_maps[i][j] == 2:
                queue.append((i, j))

    while len(queue) > 0:
        x, y = queue.pop(0)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and copied_maps[nx][ny] == 0:
                copied_maps[nx][ny] = 2
                queue.append((nx, ny))

    global answer
    zero_cnt = 0
    for i in range(n):
        zero_cnt += copied_maps[i].count(0)

    answer = max(answer, zero_cnt)


def make_wall(cnt):
    if cnt == 3:
        bfs()
        return

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


n, m = map(int, input().split())
maps = []

for i in range(n):
    temp = list(map(int, sys.stdin.readline().split()))
    maps.append(temp)

answer = 0
make_wall(0)
print(answer)

• 이 코드도 정답 처리는 가능하지만 비효율 적인 면 있음
  • 정답이 가능한 이유 : 벽을 3개 설치했때만 bfs를 돌고 가능한 케이스를 모두 해본다.
  • 비효율 적인 측면 : 현재 위치를 다음 재귀 실행시 모르기 때문에 for 문을 돌아서 현재 위치를 찾아옴

따라서 코드를 다음과 같이 수정한다.
현재위치를 기준으로
1. 벽을 세울지 안세울지 결정
2. 벽이 3개인 경우는 bfs를 돌지만 3개를 초과하는 경우는 더 볼 필요가없으니 리턴하기(사실 필요 없음 브렌치컷팅 개념으로 넣은 코드)
3. 재귀 실행시 다음번 위치가 될 부분 같이 보내기
4. 다음번 위치가 존재하지 않는다면 맵이 끝났으므로 리턴하기

코드_v2

import copy
import sys


def bfs():
    queue = []
    copied_maps = copy.deepcopy(maps)
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    for i in range(n):
        for j in range(m):
            if copied_maps[i][j] == 2:
                queue.append((i, j))

    while len(queue) > 0:
        x, y = queue.pop(0)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and copied_maps[nx][ny] == 0:
                copied_maps[nx][ny] = 2
                queue.append((nx, ny))

    global answer
    zero_cnt = 0
    for i in range(n):
        zero_cnt += copied_maps[i].count(0)

    answer = max(answer, zero_cnt)


def make_wall(r, c, cnt):
    if cnt > 3:
        return

    #  어느 시점에 벽 3개를 이미 다 세웠음. 더 볼 필요 없음
    if cnt == 3:
        bfs()
        return
    
    # 다 돌았음. cnt가 3 미만인 경우에도 더 돌 곳이 없으니 끝냄
    if r == n:
        return
        
	# 다음 실행 위치 설정(조건문 사용)
    new_c = (c + 1) % m
    new_r = r + 1 if new_c == 0 else r

    make_wall(new_r, new_c, cnt)

    if maps[r][c] == 0:
        maps[r][c] = 1
        make_wall(new_r, new_c, cnt + 1)
        maps[r][c] = 0


n, m = map(int, input().split())
maps = []

for i in range(n):
    temp = list(map(int, sys.stdin.readline().split()))
    maps.append(temp)

answer = 0
make_wall(0, 0, 0)
print(answer)

코드_v3

import copy
import sys


def bfs():
    queue = []
    copied_maps = copy.deepcopy(maps)
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    for i in range(n):
        for j in range(m):
            if copied_maps[i][j] == 2:
                queue.append((i, j))

    while len(queue) > 0:
        x, y = queue.pop(0)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and copied_maps[nx][ny] == 0:
                copied_maps[nx][ny] = 2
                queue.append((nx, ny))

    global answer
    zero_cnt = 0
    for i in range(n):
        zero_cnt += copied_maps[i].count(0)

    answer = max(answer, zero_cnt)


def make_wall(r, c, cnt):
    if cnt > 3:
        return

    #  어느 시점에 벽 3개를 이미 다 세웠음. 더 볼 필요 없음
    if cnt == 3:
        bfs()
        return

    # 다 돌았음. cnt가 3 미만인 경우에도 더 돌 곳이 없으니 끝냄
    if r == n:
        return
	
    # 다음 실행 위치 설정(계산)
    new_c = (c + 1) % m
    new_r = r + (c + 1) // m

    make_wall(new_r, new_c, cnt)

    if maps[r][c] == 0:
        maps[r][c] = 1
        make_wall(new_r, new_c, cnt + 1)
        maps[r][c] = 0


n, m = map(int, input().split())
maps = []

for i in range(n):
    temp = list(map(int, sys.stdin.readline().split()))
    maps.append(temp)

answer = 0
make_wall(0, 0, 0)
print(answer)

최적화 결과

• 코드_v1 보다 v2, v3에서 속도향상 결과 얻음