[백준] 14502 연구소(Python)

백준 - 14502 연구소

풀이

1. for문 + 재귀로 벽을 세우고 bfs => 시간 초과

def make_wall(count):
	# 점 3개를 고른 후 bfs
    if count == 3:
        bfs()
        return
    # 점 3개를 바꾸지 않은 경우 for문으로 하나씩 바꿔줌
    # for문도 비효율적인데 무조건 처음부터 다시 돌아야해서 비효율적
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 0:
                graph[i][j] = 1
                make_wall(count + 1)
                graph[i][j] = 0

2. 벽을 세우는 경우를 조합으로 구하고 bfs => 통과

=> ex) 조합: ((1, 1), (1, 3), (4, 0)), ((1, 1), (1, 3), (4, 1)), ...

오늘은 bfs코드를 조금 다르게 써봤다.
외부에서 bfs를 호출해서 방문 가능한 지점을 만나면 들어가도록 하는 코드에서, 처음부터 bfs해서 그 안에서 가능한 점을 큐에 넣어놓고 시작하는 코드로 수정했다.

기존 코드(bfs)

def bfs(x, y):
	# 시작점을 받아서 큐에 넣고 시작
    q = deque([(x, y)])
    graph[x][y] = 0
    while q:
    	...

for i in range(M):
    for j in range(M):
        if graph[i][j]:
            bfs(j, i)

수정 후 코드(bfs)

def bfs(graph):
	# 큐에 방문 가능한 점들을 미리 넣어둠
    q = deque([(j, i) for i in range(N) for j in range(M) if graph[i][j] == 2])
    while q:
  		...

---

코드

통과한 코드

from sys import stdin
from collections import deque
from copy import deepcopy
from itertools import combinations

def bfs(graph):
    q = deque([(j, i) for i in range(N) for j in range(M) if graph[i][j] == 2])
    while q:
        x, y = q.popleft()
        for nx, ny in zip([x+1, x-1, x, x], [y, y, y+1, y-1]):
            if 0 <= nx < M and 0 <= ny < N and not graph[ny][nx]:
                graph[ny][nx] = 2
                q.append((nx, ny))
    
    global answer
    count = sum([i.count(0) for i in graph])
    answer = max(answer, count)


N, M = map(int, stdin.readline().split())
graph = [list(map(int, stdin.readline().split())) for _ in range(N)]
x_y = [(x, y) for x in range(M) for y in range(N) if not graph[y][x]]
answer = 0

for c in combinations(x_y, 3):
    tmp_graph = deepcopy(graph)
    for x, y in c:
        tmp_graph[y][x] = 1
    bfs(tmp_graph)

print(answer)

시간초과 코드

from sys import stdin
from collections import deque
from copy import deepcopy

def bfs():
    tmp_graph = deepcopy(graph)
    q = deque([])
    for i in range(N):
        for j in range(M):
            if tmp_graph[i][j] == 2:
                q.append((j, i))
    while q:
        x, y = q.popleft()
        for nx, ny in zip([x+1, x-1, x, x], [y, y, y+1, y-1]):
            if 0 <= nx < M and 0 <= ny < N and not tmp_graph[ny][nx]:
                tmp_graph[ny][nx] = 2
                q.append((nx, ny))
    global answer
    count = 0
    for i in tmp_graph:
        count += i.count(0)
    answer = max(answer, count)


def make_wall(count):
    if count == 3:
        bfs()
        return
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 0:
                graph[i][j] = 1
                make_wall(count + 1)
                graph[i][j] = 0


N, M = map(int, stdin.readline().split())
graph = []

for i in range(N):
    graph.append(list(map(int, stdin.readline().split())))

answer = 0
make_wall(0)
print(answer)