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

BFS + 백트래킹 문제 

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

14502번: 연구소

 

0 - 빈 칸

1 - 벽

2 - 바이러스

 

처음에 생각한 방식 

이것도 처음에 패턴 찾아서 쌩자 구현하려 했는데, 불가능이다. 그 이유는 바이러스(2)가 벽(1)을 만날때까지 상하좌우로 이동하며 벽(0)을 바이러스(2)로 감염시키기 때문이다. 즉, 패턴을 찾을 수 없다.

 

접근 방식

• 바이러스들(2)의 위치에서 동시에 퍼져야 하므로 BFS
• 벽을 무조건 3개 세워야 하는데, 바이러스가 최대한 퍼지지 않는 방향으로 벽을 세워야 하므로 Brute Force(모든 경우의수 탐색)
• 그런데, 무작정 Brute Force 하다보면 시간초과과가 날 수도 있으므로 백트래킹 통해 조건 추가

 

💡 풀이코드 1 (pypy 성공, python 시간초과)

 

import sys
import copy
from collections import deque

n, m = map(int, sys.stdin.readline().split())
queue = deque()
graph = []
answer = 0

for i in range(n):
    l = list(map(int, sys.stdin.readline().split()))
    for j in range(m):
        if l[j] == 2:
            queue.append((i, j))
    graph.append(l)

def makeWall(cnt):
    if cnt == 3:
        bfs()
        return

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                makeWall(cnt + 1)
                graph[i][j] = 0

def bfs(): # virus 매개변수로 받아와야 나중에 queue에서 뺄 때 전역변수에 영향 X
    ny = [0, -1, 0, 1]
    nx = [1, 0, -1, 0]
    graph2 = copy.deepcopy(graph)
    virus = copy.deepcopy(queue) # # 매번 bfs 돌릴 때마다 queue에 넣고 빼므로
    visited = [[False] * m for _ in range(n)]

    while virus:
        y, x = virus.popleft()
        visited[y][x] = True # 매번 bfs 돌릴 때마다 visited 초기화 필요

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

            if 0 <= nextY < n and 0 <= nextX < m and visited[nextY][nextX] == False:

                if graph2[nextY][nextX] == 2 or graph2[nextY][nextX] == 1: continue

                visited[nextY][nextX] = True

                if graph2[nextY][nextX] == 0:
                    graph2[nextY][nextX] = 2
                    virus.append((nextY, nextX))
    count(graph2)

def count(graph2):
    global answer
    cnt = 0
    for i in range(n):
        for j in range(m):
            if graph2[i][j] == 0: cnt += 1
    answer = max(answer, cnt)
                
makeWall(0)
print(answer)

 

👩🏻‍💻 위의 코드

makeWall : 백트래킹 방식으로 그래프에서 빈칸(0)의 위치에 벽(1)을 3개 세움

• for문을 돌며 그래프에서 벽을 3개 세우는 모든 경우의 수 구현 (순열 방식)
• 벽을 3개 세웠으면 bfs 호출하여 바이러스를 퍼뜨림 -> bfs 함수 내에선 count 함수 호출하여 바이러스가 최종적으로 모두 퍼진 후(벽을 만날 때까지) 남아있는 빈칸(0)의 갯수를 셈.
• bfs 리턴 뒤엔 벽(1)으로 만들어준 해당 위치를 다시 빈 칸(0)으로 원복시킴 

bfs : makeWall에서 벽을 3개 세웠다면 해당 그래프에서 바이러스를 모두 퍼뜨리는 역할 (벽을 만나 끝날 때까지)

• graph를 deepcopy하여 graph2 생성 (bfs 함수에선 바이러스를 모두 퍼뜨리므로 graph를 깊은복사해서 사용해야 함, makeWall 함수에서 추후에 graph를 이용하여 다시 새로운 경우의 수를 만들어내야하므로)
• 초기 바이러스 위치를 담은 queue도 deepcopy하여 사용 (매번 bfs 돌릴 때마다 queue에서 값을 넣고 빼야 하므로, 만약 deepcopy하지 않고 사용하게 되면 다음 bfs를 돌릴 땐 비어있는 queue를 이용하여 bfs 돌리게 됨.)
• 처음엔 queue를 deepcopy하지 않고, 매개변수로 받아 사용했었음. 하지만, 매개변수로 받아 값을 변경해도 결론적으로 전역변수 값이 변경되므로 똑같은 문제 발생 -> bfs함수에서 초기에 매번 graph에서 바이러스 위치를 추출하는 방식으로 구현하거나 queue를 deepcopy하는 방식으로 무조건 구현해야함
• 매번 bfs를 돌리므로 visited의 변수 선언 위치 : 전역 -> bfs 함수 내부로 변경
• graph2가 빈칸이라면 graph2를 바이러스로 만들어주고, virus에 해당 위치 삽입. -> 결론적으로 virus[]에는 바이러스(2)의 좌표값만 들어가게 됨.
• 사실 아래 코드는 불필요한 코드임. 우리는 graph2[nextY][nextX]가 0일 때만 로직 실행(바이러스로 만들어주고 queue에 삽입)하므로 굳이 아래와 같은 코드를 넣을 필요가 없음. 둘다 if문으로 작성했기 때문에 굳이 조건문 확인을 한번 더하게 됨.

if graph2[nextY][nextX] == 2 or graph2[nextY][nextX] == 1: continue
	visited[nextY][nextX] = True

 

count : bfs 함수를 통해 바이러스가 퍼진 후 해당 그래프에서 빈칸(0)의 갯수를 세는 역할

• bfs()에서 바이러스를 모두 퍼트린 뒤 해당 그래프를 인자로 넘겨줌.
• max()를 통해 빈칸의 최대 갯수 update 여부 판별

 

💡 풀이코드 2 (pypy 성공, python 성공)

import sys
import copy
from collections import deque

n, m = map(int, sys.stdin.readline().split())
queue = deque()
graph = []
answer = 0
ny = [0, -1, 0, 1]
nx = [1, 0, -1, 0]

for i in range(n):
    l = list(map(int, sys.stdin.readline().split()))
    for j in range(m):
        if l[j] == 2:
            queue.append((i, j))
    graph.append(l)

def makeWall(start, cnt):
    if cnt == 3:
        bfs()
        return

    for i in range(start, n * m): # 2차원 배열 -> 1차원 배열로 변경하여 조합
        r = i // m
        c = i % m

        if graph[r][c] == 0:
            graph[r][c] = 1
            makeWall(i + 1, cnt + 1)
            graph[r][c] = 0

def bfs(): 
    graph2 = copy.deepcopy(graph)
    virus = copy.deepcopy(queue) 

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

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

            if 0 <= nextY < n and 0 <= nextX < m:
                if graph2[nextY][nextX] == 0:
                    graph2[nextY][nextX] = 2
                    virus.append((nextY, nextX))
    count(graph2)

def count(graph2):
    global answer
    answer = max(answer, sum(i.count(0) for i in graph2))
         
makeWall(0, 0)
print(answer)

 

개선 사항

makeWall : 순열 방식 -> 조합 방식으로 변경

• 기존의 makeWall이 순열 방식이였기 때문에 pypy에선 통과했지만, python에선 시간초과가 났다. -> 조합 방식으로 변경하니 pypy, python에서 둘다 통과
• 사실 파이썬에서 제공하는 combinations 라이브러리 사용하면 되지만, 어떻게든 라이브러리를 덜 사용하고 구현하고 싶어서 기존의 코드에서 수정하는 방식으로 구현
• 조합을 하려면 인자로 begin(for문 돌릴 시작 위치)를 추가로 받으면 됨. 하지만 graph가 2차원 배열이므로 시작 위치를 지정하기 애매하므로 2차원 배열 -> 1차원 배열로 변경하여 구현
• for문을 잘 보면 range가 start에서 n * m으로 변경된 걸 볼 수 있음. 1차원 배열로 변경했으므로 n * m까지 for문을 돌려야함

for i in range(start, n * m): # 2차원 배열 -> 1차원 배열로 변경하여 조합
        r = i // m
        c = i % m

        if graph[r][c] == 0:
            graph[r][c] = 1
            makeWall(i + 1, cnt + 1)
            graph[r][c] = 0

• r은 index에서 m(col)을 나눈 값으로 row를 의미한다.
• c는 index에서 m(col)의 나머지 값으로 column을 의미한다.
• makeWall을 재귀로 돌릴 땐, 시작 위치를 현재 index + 1로 지정해주므로, 기존의 경우의수가 중복되던 문제를 피할 수 있다. -> bfs 호출 횟수도 확연히 주므로 결론적으로 시간, 메모리 감소

bfs : 불필요한 visit 배열, 조건식(if graph2[nextY][nextX] == 2 or graph2[nextY][nextX] == 1: continue) 제거

 

count : 파이썬에서 제공하는 count, sum 함수를 사용하여 기존의 코드를 한줄로 줄임.

def count(graph2):
    global answer
    answer = max(answer, sum(i.count(0) for i in graph2))

 

결론 

• 시간 : 3248ms -> 2908ms로 빨라짐
• 메모리 : 132512KB -> 34140KB로 대략 4배 감소

 

*참고

https://great-park.tistory.com/104

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

https://mentha2.tistory.com/24

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

https://door-of-tabris.tistory.com/entry/%EB%B0%B1%EC%A4%80-14502%EB%B2%88-%EC%97%B0%EA%B5%AC%EC%86%8C%ED%8C%8C%EC%9D%B4%EC%8D%AC#google_vignette

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