백준 14502 연구소 - 골드5 [파이썬]

항상 자바로 풀다가 파이썬으로 그래프 문제를 풀어봤다.

이 문제에서 배운 점:

 

1. import copy 해서 2차원 배열을 deepcopy 하는 방법은 slicing 해서 복사 하는 것보다 훨씬 느리다는 점.

(deepcopy를 사용하면 3136ms, 사용하지 않으면 1676ms 가 나왔다.)

 

2. 자바로 풀던때가 적응돼서 visited 배열을 꼭 따로 만들어줬었는데, 그럴필요 없다는 점

 

3. append 할 때 [nr, nc] 처럼 리스트가 아니라 (nr, nc) 해서 튜플로 해주면 더 빠르다는점.

(리스트 썼을 때 1860ms, 튜플로 썼을 때 1676ms 가 나왔다.)

 

4. import time 이란걸 사용해서 꼭 백준에 제출하지 않더라도 코드 실행시간을 체크할 수 있다는 점을 알았다.

import sys
# import copy
# import time
from collections import deque
# start = time.time()
input = sys.stdin.readline
R, C = map(int, input().split())
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
mmap = []
answer = 0
for i in range(R):
    mmap.append(list(map(int, input().split())))


def bfs():
    queue = deque()
    tmap = [m[:] for m in mmap]
    # tmap = copy.deepcopy(mmap)
    for i in range(R):
        for j in range(C):
            if tmap[i][j] == 2:
                queue.append((i, j))

    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 > nr or nr >= R or 0 > nc or nc >= C:
                continue
            if tmap[nr][nc] == 0:
                tmap[nr][nc] = 2
                queue.append((nr, nc))

    global answer
    cnt = 0
    for i in range(R):
        cnt += tmap[i].count(0)
    answer = max(answer, cnt)


def backtrack(cnt):
    if cnt == 3:
        bfs()
        return
    for i in range(R):
        for j in range(C):
            if mmap[i][j] == 0:
                mmap[i][j] = 1
                backtrack(cnt+1)
                mmap[i][j] = 0


backtrack(0)
print(answer)
# print("time : ", time.time() - start)