삼성 SW역량테스트 기출 / 2017 상반기 오후 2번 문제 방화벽 설치하기 - BFS, 조합(백트래킹), 완전탐색 / Python 파이썬

 

*문제 출처는 삼성전자, 코드트리에 있습니다.

 

삼멘 5일차

문제 제목: 방화벽 설치하기

문제 사이트: https://www.codetree.ai/training-field/frequent-problems/problems/firewall-installation/description?page=3&pageSize=20&statuses=Ready%2CIn+Progress

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

---

방화벽의 위치를 조합으로 해서 완전탐색으로 구해줬다.

불이 나는 상황은 BFS로 구현해줬다.

 

문제 풀면서 메모리 초과가 계속 났었는데,

이전에 문제 풀때랑 동일하게 maps 를 copy 하는 과정에서 메모리초과가 계속 떴다.

이걸 방지하려면 그냥 maps 자체에서 (전역)계속 수정했다가 원상태로 복귀시키는 코드로 구현해야함..

 

 

나의 풀이

from collections import deque

n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
answer = float('-inf')
empty = []  # 0
wall = []  # 1
fires = []  # 2

for i in range(n):
    for j in range(m):
        if maps[i][j] == 0:
            empty.append([i, j])
        elif maps[i][j] == 1:
            wall.append([i, j])
        elif maps[i][j] == 2:
            fires.append([i, j])

def BFS(walls):  # 불이 번지는 것은 BFS
    global answer

    # 선택한 벽을 임시로 세운다
    for x, y in walls:
        maps[x][y] = 1
    
    queue = deque(fires)
    while queue:
        qx, qy = queue.popleft()

        directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
        for dx, dy in directions:
            xx, yy = qx + dx, qy + dy

            if 0 <= xx < n and 0 <= yy < m and maps[xx][yy] == 0:
                maps[xx][yy] = 2
                queue.append((xx, yy))
    
    # BFS가 끝난 후, 남은 빈 공간 갯수를 갱신한다
    tmp_empty = 0
    for i in range(n):
        for j in range(m):
            if maps[i][j] == 0:
                tmp_empty += 1
    answer = max(answer, tmp_empty)
    # 원래 상태로 맵을 복구한다
    for x, y in walls:
        maps[x][y] = 1
    for x, y in empty:
        maps[x][y] = 0
    for x, y in fires:
        maps[x][y] = 2

def combination(length, arr, c):
    if len(arr) == length:
        BFS(arr)
        return
    for i in range(c, len(empty)):
        combination(length, arr + [empty[i]], i + 1)

combination(3, [], 0)

print(answer)

 

백준 연구소 문제와 유사하다. 문제 푼적 있는거같은데 포스트는 어디갔지..ㅠㅠ

---

※ 알아야 할 것

- 메모리 초과가 나면 그냥 maps를 하나로 두고 다시 원상태로 복귀시키자