풀었지만 만족스럽지 못한 (골드 5)

#14502번 연구소 https://www.acmicpc.net/problem/14502

14502번: 연구소

잘 풀었다.

import sys 
input = sys.stdin.readline
N, M = map(int, input().split())

maps = []
viruses = []
walls = []
zeros = []
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(M):
        if tmp[j] == 1:
            walls.append([i, j])
        elif tmp[j] == 2:
            viruses.append([i, j])
        elif tmp[j] == 0:
            zeros.append([i, j])
    maps.append(tmp)


# 바이러스 퍼뜨리기
def go_virus(maps):
    n_v = len(viruses)
    visited = [[False]*M for _ in range(N)]
    for a, b in viruses:
        que = [[a, b]]
        visited[a][b] = True
        while que:
            x, y = que.pop(0)

            for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and maps[nx][ny] == 0:
                    visited[nx][ny] = True
                    que.append([nx, ny])
                    n_v += 1
    return n_v


answer = 0

# 벽의 경우의 수 조합하기


def solve(maps, cnt, idx):
    global answer
    if cnt == 3:
        # 벽이 세개일 경우 안전 영역 계산하기
        result = N*M - len(walls) - 3 - go_virus(maps)
        if answer < result:
            answer = result
        return result

    for i in range(idx, len(zeros)):
        x, y = zeros[i]
        maps[x][y] = 1
        solve(maps, cnt+1, i+1)
        maps[x][y] = 0


solve(maps, 0, 0)
print(answer)

근데 중간에 엄청 꼬였었다. 그래서 다른 블로그를 조금 참고했는데,

그분과 나의 차이는 "기록"이었다.

 

나는 처음 문제를 보고 대충 예상한 풀이과정을 머리속에서 해결한다.

하지만 내가 봤던 블로그는 문제의 풀이순서를 명시적으로 작성한 뒤 코드를 작성한다.

 

위 문제의 경우는

1. 벽을 선택하는 경우의 수 구현

2. 바이러스 퍼뜨리기

3. 생존 구역 계산

 

과 같은 순서로 진행할 수 있다.

 

아주 사소한 습관이지만

생각보다 큰 영향을 미친다.

 

다시금 떠오르는 말이다.

기록은 기억을 지배한다.