[BOJ] 14502. 연구소 Python

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

 

1. 해결방법

그래프 완전 탐색문제이다.

1. 먼저 벽을 3개 쳐야하므로, 백트래킹을 이용하여 빈 공간(0)에 벽을 3개 친다.
2. 벽을 쳤으면, BFS를 통해서 바이러스 부분이 퍼져나가는 로직을 구현한다.
3. BFS를 다 돌았아면, 연구소의 넓이를 구한다.

새롭게 배운 부분은, 기존에 사용하던 백트래킹 로직에서 for문을 많이 사용하게 되어서 시간초과가 나온다.
해결방법은 '//'와 '%'의 연산을 이용해서 하나의 for문을 통해 가지치기를 진행해준다.

 

 

2. 정답코드

import sys
from collections import deque
from copy import deepcopy
input = sys.stdin.readline


N, M = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(N)]
dy, dx = (1, -1, 0, 0), (0, 0, 1, -1)

virus = []
one, two = 0, 0
for i in range(N):
    for j in range(M):
        if maps[i][j] == 2:
            virus.append((i, j))
            two += 1
        elif maps[i][j] == 1:
            one += 1

zero = N * M - one - two


def bfs(new_maps, zero):
    q = deque(virus)

    while q:
        ey, ex = q.popleft()

        for d in range(4):
            ny, nx = ey + dy[d], ex + dx[d]
            if 0 <= ny < N and 0 <= nx < M and new_maps[ny][nx] == 0:
                new_maps[ny][nx] = 2
                q.append((ny, nx))
                zero -= 1
    return zero


def dfs(start, depth):
    global answer, zero

    if depth == 3:
        new_maps = deepcopy(maps)
        answer = max(answer, bfs(new_maps, zero - 3))
        return

    for i in range(start, N * M):
        row = i // M
        col = i % M
        if maps[row][col] == 0:
            maps[row][col] = 1
            dfs(i, depth + 1)
            maps[row][col] = 0


answer = -1e9
dfs(0, 0)
print(answer)