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

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

14502번: 연구소

가장 전형적인 DFS BFS로

알고리즘을 푸는 문항입니다.

 

문제 알고리즘은 다음과 같습니다.

 

1. 벽을 3개까지 세운다

2 바이러스를 퍼트린다.

3. 안전영역 각각을 구한다.

 

이 문제를 처음 접했다면

dfs로 어떻게 벽을 구할지는 대강 감이 오셔도

그 다음이 문제입니다.

빈칸에 벽을 3개 설치해야하는데

빈칸이 만약 총 25개라면

25C3(25 com 3)의 케이스를 구해야합니다.

이걸 일일이 손으로 볼 순 없고...

그래서 사용하는 것이 백트래킹입니다.

직접 코드를 보고 이야기했습니다.

 

 

# 백준 14502번 연구소
from collections import deque
from copy import deepcopy

N, M = map(int, input().split())

graph = []
virus_s = []
for i in range(N):
    data = list(map(int, input().split()))
    graph.append(data)
    for j in range(M):
        if data[j] == 2:
            virus_s.append([i, j])

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

max_safe = 0


def bfs():
    global max_safe
    visited = [[False] * M for _ in range(N)]
    temp = deepcopy(graph)
    for virus in virus_s:
        v_x, v_y = virus
        if visited[v_x][v_y] == True:
            continue
        q = deque()
        q.append([v_x, v_y])
        visited[v_x][v_y] = True

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

            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                # 범위
                if nx < 0 or nx >= N or ny < 0 or ny >= M:
                    continue
                # 이미 방문
                if visited[nx][ny] == True:
                    continue
                # 벽으로 막혀있음
                if temp[nx][ny] == 1:
                    continue

                if (temp[nx][ny] == 0 or temp[nx][ny] == 2) and visited[nx][ny] == False:
                    visited[nx][ny] = True
                    temp[nx][ny] = 2
                    q.append([nx, ny])

    now_safe = sum(i.count(0) for i in temp)

    max_safe = max(max_safe, now_safe)


def dfs(num):
    if num == 3:
        bfs()
        return

    for x in range(N):
        for y in range(M):
            if graph[x][y] == 0:
                graph[x][y] = 1
                dfs(num + 1)
                graph[x][y] = 0
                # 백트래킹의 가장 중요한 것-->다시 원상태로 돌려주기


dfs(0)
print(max_safe)

 

이 코드의 경우에는

pypy3로는 통과하지만

python3로는 시간초과가 발생합니다.

그 이유는 벽을 구하는 케이스가 너무 오래걸리기 때문.

for문을 일단 전부 다 돌기 때문에

시간이 오래걸리는 편.

https://mentha2.tistory.com/24

[백준] 14502번: 연구소 풀이 with Python

여기있는 코드를 보면

벽을 구할 때에도

시간을 단축시키는 코드가 있습니다.

이 분은 조금 독특하게

시간을 단축시키는 코드를 구상했네요.

대단하다...ㄷㄷ

 

+++

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

dx=[1,-1,0,0]
dy=[0,0,1,-1]

N,M=map(int,input().split())
graph=[]
wall=[]
virus=[]
for i in range(N):
    data=list(map(int,input().split()))
    for j in range(M):
        if data[j]==0:
            wall.append([i,j])
        elif data[j]==2:
            virus.append([i,j])

    graph.append(data)

wall_case=combinations(wall,3)

answer=0

for walls in wall_case:

    temp=deepcopy(graph)
    for w in walls:
        wx,wy=w
        temp[wx][wy]=1
    visited=[[False]*M for _ in range(N)]
    q=deque()
    for v in virus:
        vx,vy=v
        q.append([vx,vy])
        visited[vx][vy]=True
    while q:
        x,y=q.popleft()

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

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue
            if visited[nx][ny]==True:
                continue
            if temp[nx][ny]==1:
                continue
            visited[nx][ny]=True
            q.append([nx,ny])
            temp[nx][ny]=2

    safe=0
    for x in range(N):
        safe+=temp[x].count(0)

    answer=max(answer,safe)


print(answer)

combination을 활용한 풀이법입니다.

굳이?이렇게 까지 풀 필요가 있는가 싶긴하지만

빈칸이 있는 곳에는

벽을 놓을 수 있으니

wall에 다가 모든 빈칸의 좌표를 넣고

combination 3을 시켜줍니다.

그리고 각 벽이 있는 케이스대로

벽이 있다고 가정하고

계속 풀어주는 경우입니다.

이 풀이법은 python3로도 시간초과에 걸리지 않습니다.