[백준알고리즘] 14502번: 연구소 -Python

[백준알고리즘] 14502번: 연구소 -Python

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

14502번: 연구소

20200423 아래에 PyPy3로만 통과한 코드를 추가했다. PyPy로만 통과가 됐지만, 더 보기 편한거같아서 추가했다.

---

이런류의 브루트 포스에 약한 것 같다.

'브포밖에 방법이 없나?'라는 생각만 하면서 시간이 많이 지나고 섣불리 못 덤빈다.

 

이 문제의 경우에는 메모리도 넉넉하고 브루트 포스를 하더라도 최대 범위가 8x8이기 때문에 충분한 시간에 통과할 수 있다. 하지만 2를 칠해봐야 하는 시간, 0의 개수를 세는 시간까지 포함되어야 하기 때문에 맞는 방법일까 하고 너무 오래 고민한다.

 

브루트 포스로 문제를 푼다는 것만 안다면 크게 어렵지 않게 풀 수 있다. 좌표 위에 벽을 놓는 구간을 모두 3군데 정하는 알고리즘을 구현하고, 3개의 벽을 모두 두면 바이러스가 퍼진 상황을 그린다. 그리고 바이러스가 닿지 않는 영역의 크기를 구하면 된다.

 

벽 3개의 위치를 정하는 과정은 중복을 피하기 위해서 방금 전의 위치를 항상 인자로 넘겨주면서 해당 좌표 이후부터 찾기 시작하도록 했다.

바이러스가 퍼지는 상황은 BFS를 사용해서 구현했다.

from collections import deque

def bfs():
    global remain
    
    t_table = []
    for t in table:
        t_table.append(t[:])

    two = deque([])
    for i in range(n):
        for j in range(m):
            if t_table[i][j] == 2:
                two.append((i, j))
    while two:
        p, q = two.popleft()
        for d in range(4):
            x, y = p + dx[d], q + dy[d]
            if 0<=x<n and 0<=y<m and t_table[x][y] == 0:
                t_table[x][y] = 2
                two.append((x, y))
    
    c = 0
    for t in t_table:
        c += t.count(0)
    remain = max(c, remain)
    return

def wall(depth, x=0, y=0):
    global table
    if depth == 3:
        bfs()
        return
    
    for i in range(y, m):
        if table[x][i] == 0:
            table[x][i] = 1
            wall(depth+1, x, i)
            table[x][i] = 0
    for i in range(x+1, n):
        for j in range(m):
            if table[i][j] == 0:
                table[i][j] = 1
                wall(depth+1, i, j)
                table[i][j] = 0

n, m = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(n)]
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
remain = 0

wall(0)
print(remain)

20200423

새롭게 풀어봤는데 Python3로는 시간초과가 발생했고 PyPy3로만 통과했다.

하지만 위의 코드보다 더 보기 깔끔해서 올려보았다.

from collections import deque

n, m = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(n)]
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
virus = []
for i in range(n):
    for j in range(m):
        if table[i][j] == 2:
            virus.append((i, j))

def solve(wall):
    global ans
    if wall == 3:
        # 바이러스 확산
        visited = [[False] * m for _ in range(n)]
        queue = deque(virus[:])
        for qi, qj in queue:
            visited[qi][qj] = True
        while queue:
            qi, qj = queue.popleft()
            for d in range(4):
                x, y = qi+dx[d], qj+dy[d]
                if 0<=x<n and 0<=y<m and not visited[x][y] and table[x][y] == 0:
                    visited[x][y] = True
                    queue.append((x, y))

        # 안전영역 검사
        cnt = 0
        for i in range(n):
            for j in range(m):
                if table[i][j] == 0 and not visited[i][j]:
                    cnt += 1
        ans = max(ans, cnt)
        return

    for i in range(n):
        for j in range(m):
            if table[i][j] == 0:
                table[i][j] = 1
                solve(wall + 1)
                table[i][j] = 0

ans = 0
solve(0)
print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다