[백준] 14502번 연구소 - 파이썬

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

14502번: 연구소

풀이:

bfs를 사용해야 한다는 것은 눈치챌 수 있었지만 벽을 놓는 조건을 어떻게 구현해야 할지 생각하느라 어려웠다.

처음에는 규칙이 존재하는 줄 알고 조건을 하나하나 적으려고 했지만 경우의 수가 너무 많음을 깨달았다.

그래서 벽을 쌓고 bfs로 탐색하는 과정을 계속 반복하여 모든 경우의 수를 체크하는 방법을 생각했지만 뭔가 이렇게 되면 시간 초과가 날 것 같았다.

그리고 모든 경우의 수를 고려하여 벽을 쌓는 코드를 어떻게 구현해야 할지 몰랐다.

 

구글링으로 재귀를 사용하면 된다는 걸 배웠다.

하지만 생각한 데로 python3로 하니 시간이 초과하여 더욱 빠른 pypy3을 사용할 수밖에 없었다.

 

결국 다시 구글링을 하니 파이썬에는 combination(조합)을 지원하는 모듈이 있다는 걸 배웠다.

재귀를 사용하게 되면 permutaion(순열)의 방식이어서 시간 초과가 나는 것 같다.

그래서 combination을 사용하니 python3로도 통과가 되었다.

알고리즘 공부는 갈길이 멀다...

 

재귀를 사용한 코드:

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

def bfs():
    queue = deque()
    trial = copy.deepcopy(grid)
    for i in range(len(virus)):
        queue.append(virus[i])

    while queue:
        y, x = queue.popleft()

        for i in range(4):
            ny = dy[i] + y
            nx = dx[i] + x

            if ny <= -1 or ny >= n or nx <= -1 or nx >= m:
                continue
            if trial[ny][nx] == 0:
                trial[ny][nx] = 2
                queue.append([ny, nx])

    global safe
    safe_current = 0

    for i in range(n):
        safe_current += trial[i].count(0)

    safe = max(safe, safe_current)


def walls(count):
    if count == 3:
        bfs()
        return

    for y in range(n):
        for x in range(m):
            if grid[y][x] == 0:
                grid[y][x] = 1
                walls(count + 1)
                grid[y][x] = 0


n, m = map(int, input().split())
grid = []
virus = []
safe = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(n):
    grid.append(list(map(int, input().split())))

for y in range(n):
    for x in range(m):
        if grid[y][x] == 2:
            virus.append([y, x])

walls(0)
print(safe)

 

combination을 사용한 코드:

import sys
import copy
from collections import deque
from itertools import combinations
input = sys.stdin.readline

def bfs():

    for i in combinations(blank, 3):
        queue = deque()
        trial = copy.deepcopy(grid)

        for y, x in i:
            trial[y][x] = 1

        for i in range(len(virus)):
            queue.append(virus[i])

        while queue:
            y, x = queue.popleft()

            for i in range(4):
                ny = dy[i] + y
                nx = dx[i] + x

                if ny <= -1 or ny >= n or nx <= -1 or nx >= m:
                    continue
                if trial[ny][nx] == 0:
                    trial[ny][nx] = 2
                    queue.append([ny, nx])

        global safe
        safe_current = 0

        for i in range(n):
            safe_current += trial[i].count(0)

        safe = max(safe, safe_current)


n, m = map(int, input().split())
grid = []
virus = []
blank = []
safe = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(n):
    grid.append(list(map(int, input().split())))

for y in range(n):
    for x in range(m):
        if grid[y][x] == 2:
            virus.append([y, x])
        if grid[y][x] == 0:
            blank.append([y, x])

bfs()
print(safe)