[백준]14502.연구소

문제

14502.연구소

성능 요약

메모리: 119060 KB, 시간: 452 ms

분류

너비 우선 탐색(bfs), 브루트포스 알고리즘(bruteforcing), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 구현(implementation

분석

과거에 제출한 코드와 현재 코드와의 차이는 딱히 없었다..
과거 코드는 BFS 함수 안에서 for문을 돌린 것, 현재 코드는 BFS함수엔 BFS 로직만 들어있는 것
개인적으로 코드의 재사용성을 위해(알고리즘에선 무의미하지만...) 현재 코드처럼 작성하는 것이 바람직하다고 생각한다.

과거의 코드를 보니 알고리즘 스터디를 할 때 배웠던 슬라이싱을 이용했다.
현재 코드에 적용해 차이를 확인하니
slicing 사용 : 메모리 33192KB, 시간 2736ms
deepcopy 사용 : 메모리 32884KB, 시간 4032ms
slicing을 이용했을 때 시간이 25%정도 감소하는 것을 볼 수 있다.
대신 deepcopy가 메모리측에선 효율적인 것 같다.

😊What I Learned

check_temp = [check[i][:] for i in range(N)]
슬라이싱을 이용해 copy가 가능하다!
물론 얕은복사이기에 2차원배열에선 전체를 슬라이싱 하지 않고
위 코드처럼 for문을 이용해 안 쪽의 리스트를 복사해 주어야한다.
 

💻CODE

import sys
from itertools import combinations
from collections import deque

#BFS
def BFS(w1,w2,w3):
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    cnt = 0
    # deepcopy와 slicing
    # check_temp = deepcopy(check)
    check_temp = [check[i][:] for i in range(N)]
    q = deque(start)
    check_temp[w1[0]][w1[1]] = check_temp[w2[0]][w2[1]] = check_temp[w3[0]][w3[1]] = False
    
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0<=nx<N and 0<=ny<M and check_temp[nx][ny] and not MAP[nx][ny]:
                q.append([nx,ny])
                check_temp[nx][ny] = False
                
    for i in check_temp:
        cnt += i.count(True)
        
    return cnt



# 입력
N, M= map(int,sys.stdin.readline().split())
MAP = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# 변수 setting
check = [[False]*M for _ in range(N)]
wall = []
start = []
result = 0

# MAP에서 start 위치와 빈 벽 확인
for i in range(N):
    for j in range(M):
        if not MAP[i][j]:
            wall.append((i,j))
            check[i][j] = True
        elif MAP[i][j] == 2:
            start.append((i,j))

# 벽 3개 만들 수 있는 경우의 수 모두 모여라! 조합 함수 이용
wall = list(combinations(wall, 3))

# 모든 경우의 수 확인 : BFS
for w in wall:
    w1, w2, w3 = w
    # 사실 BFS and에 의해서 벽(1)으로 바꿔주는 것이 무의미하지만
    # 디버깅하기 좋기 위해서 벽(1)으로 바꿔주었다.
    MAP[w1[0]][w1[1]] = MAP[w2[0]][w2[1]] = MAP[w3[0]][w3[1]] = 1
    temp = BFS(w1,w2,w3)
    MAP[w1[0]][w1[1]] = MAP[w2[0]][w2[1]] = MAP[w3[0]][w3[1]] = 0
    
    if temp > result:
        result = temp
    

print(result)