728x90
*문제 출처는 삼성전자, 코드트리에 있습니다.
삼멘 5일차
문제 제목: 방화벽 설치하기
방화벽의 위치를 조합으로 해서 완전탐색으로 구해줬다.
불이 나는 상황은 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를 하나로 두고 다시 원상태로 복귀시키자
728x90
'coding test - python > SAMSUNG SWT(SW역량 테스트)' 카테고리의 다른 글
삼성 SW역량테스트 기출 / 2018 하반기 오후 2번 문제 전투로봇 - BFS / Python 파이썬 (5) | 2024.09.26 |
---|---|
삼성 SW역량테스트 기출 / 2015 하반기 2번 문제 2개의 사탕 - BFS, 중력, 백트래킹 / Python 파이썬 (1) | 2024.09.20 |
삼성 SW역량테스트 기출 / 2019 상반기 오후 2번 문제 바이러스 백신 - BFS, 조합 / Python 파이썬 (8) | 2024.09.19 |
삼성 SW역량테스트 기출 / 2018 상반기 오후 2번 문제 병원 거리 최소화하기 - 조합 / Python 파이썬 (4) | 2024.09.19 |
삼성 SW역량테스트 기출 / 2018 하반기 오전 2번 문제 토스트 계란들 - BFS / Python 파이썬 (3) | 2024.09.17 |