[백준][그래프] No.14502_연구소 01

 

14502번: 연구소

평범한 그래프 BFS 문제이다. 백준 2178번 미로와 비슷한 느낌이다.

'미로' 문제에서는 1이 이동 가능한 칸, 0이 이동 불가능한 칸이었다.

'연구소' 문제에서는 0이 이동 가능한 칸, 1이 이동 불가능한 칸이라는 차이점이 있다.

또한 미로에서는 정해진 위치 (1, 1)에서만 시작을 했다.

연구소에서는 정해진 위치 없이 2 값이 들어있는 모든 위치에 동시에 시작을 해야 한다.

 

이 BFS 문제에서 얻고자 하는 정답(출력)이 무엇인지 알아보면,

경우에 따라 벽을 세우고,  BFS로 0을 전부 2로 바꾼 다음, 남아있는 0의 개수를 센다.

이때 0의 개수가 최대가 될 때, 0의 개수를 물어보는 문제이다.

 └ 문제 성격상 BFS든 DFS든 상관없어 보이지만, 재귀 깊이 때문에 BFS로 해당 문제를 고려했다.

 

연구소 문제를 해석하면서 가장 의문인 점이 두 가지가 있었다.

하나는 바이러스(2)가 있는 곳은 동시다발적으로 퍼져야 할텐데... 이를 어떻게 구현하지?였고,

다른 하나는 조건에서 무조건 3개의 벽을 세워야 한다는데... 이게 제한 시간 내에 가능할까?였다.

 

# Pseudo Code BFS
dfs BFS():
    queue = [ ''' somthing elements ''' ]
    
    while queue:
        tmp = queue.popleft()
        
        if tmp not visit:
            tmp = visit True
            queue.append(tmp)

의문을 하나하나 생각해보자. 위처럼 BFS의 수도 코드를 작성하고 생각했다.

그리고 곧 첫 번째 의문은 굉장히 멍청한 의문이었음을 깨달았다...

처음에는 모든 바이러스가 동시다발적으로 일어나야 하니까 멀티스레드 구현을 해야 하나?라고 생각했다.

하지만 이 문제는 바이러스가 얼마나 빨리 퍼지는지에 대한 문제가 아니다.

'바이러스가 퍼진 뒤' 남아있는 공간을 세는 문제이다.

따라서  BFS나 DFS로 그래프를 전부 탐색한 다음, 남아있는 0을 세면 된다.

 

또한, BFS 코드 특성상 들어온 순서대로 하나씩 처리를 한다.

위의 그림을 예로 들어보자면, 녹색 부분이 바이러스 부분이라고 가정해보자. 이때 벽은 없다.

그 다음으로 퍼져나간 곳이 빨강이고, 그 다음으로 퍼져나간 곳이 파랑이다.

이때 한 바이러스 부분을 먼저 계속해서 깊이 탐색해 나가지 않는다. (이는 DFS이다.)

'녹 > 녹 > 녹 > 빨 > 빨 > 빨 > 빨 > ... > 파 > 파' 이런식으로 들어온 순서대로 탐색을 진행한다.

사실... 남아있는 0의 개수만을 고려하는 문제이기에 애초에 큰 상관이 없었다.

 

from itertools import combinations

all_number_of_case = [ ''' something elements ''' ]

combinations(all_number_of_case, length)

다른 의문 하나는, 시간 초과에 대한 의문이다.

문제를 읽어보면 "벽의 개수는 3개이며, 꼭3개를 세워야 한다."라고 하는 조건이 있다.

하지만 어디에 어떻게 3개를 세우라는 말은 없으니, 브루트포스 문제라고 생각했다.

그리고 정확하게 알고리즘 분류에 브루트포스 알고리즘이 들어있었다.

(갈수록 문제를 정확하게 읽는 것 같아 성장하는 느낌이 든다.)

브루트포스가 떠오르자마자 생각난 방법은 파이썬 라이브러리를 사용하는 방법이었다.

(빠르기도 하지만, 백트래킹 구현을 많이 하지 않아서 자신이 없어 가장 먼저 떠오른 것 같다.)

 

입력 조건을 살펴본다면 가로 세로의 길이는 최소 3, 최대 8이다.

최악의 경우 8 * 8 사이즈에서 바이러스가 하나만 있는 경우이다.

63칸에서 3개의 벽을 세울 수 있는 경우의 수는 63_C_3으로 39,711가지이다.

만 단위정도라면 제한 시간 2초 내에 충분히 계산이 가능하리라 생각했다.

 

# ---------- Import ----------
from itertools import combinations
from collections import deque
import sys
input = sys.stdin.readline

가장 먼저 Import 부분을 작성해주었다.

조합 계산에 사용할 combinatinos, 그래프 계산에 사용할 deque, 빠른 입력을 위한 sys를 사용한다.

 

# ---------- Function ----------
def BFS(row: int, col: int, lab: list) -> int:
    result = 0

    return result

# ---------- Main ----------
row, col = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(row)]

result = BFS(row, col, lab)
print(result)

그리고 Function을 간단하게, Main 부분을 상세하게 작성해주었다.

코딩을 시작할 때는 늘 이런 방식으로 Import와 Main 틀을 작성하고, 함수들을 작성한다.

comprehension으로 연구소(lab) 2차원 배열을 입력받는다.

result에 BFS를 계산한 결과를 넣고 출력한다.

 

# ---------- Function ----------
def BFS(row: int, col: int, lab: list) -> int:
    result = 0
    
    # UP, DN, LFT, RHT
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

BFS에서 row, col, lab을 입력받는다.

최종 결과를 저장할 result 변수를 선언한다.

많은 BFS 문제를 풀어봤다면 익숙할 네 방향으로 이동하기 위한 dx, dy 리스트도 선언해준다.

 

# ---------- Import ----------
import copy

# ---------- Function ----------
# Checking empty(0) area that can be build a wall
empty_space = [(x, y) for x in range(row) for y in range(col) if lab[x][y] == 0]

for empty in combinations(empty_space, 3):
    graph = copy.deepcopy(lab)

    # Build a wall using combinations
    for wallX, wallY in empty:
        graph[wallX][wallY] = 1

    # Checking virus(2) area    
    queue = deque([(x, y) for x in range(row) for y in range(col) if graph[x][y] == 2])

lab에서 우선 빈 공간(0)의 위치들을 알아내야 한다. 그래야 combinations으로 조합이 가능하기 때문이다.

comprehension으로 (x, y)를 알아낸 뒤, empty_space에 저장한다.

그리고 for문으로 가능한 모든 조합의 수에 대해서 반복을 진행한다.

이때 BFS를 진행해야 하는데, 한 번 진행하고 나면 기존 BFS는 없어지기에 이를 유지할 필요가 생겼다.

파이썬의 copy 라이브러리를 사용하여 기존의 lab을 유지해준다.

 └ graph = lab을 해주면 이는 얕은 복사라 값이 같이 바뀐다. 깊은 복사를 위해 deepcopy를 해줘야 한다.

 

이러면 empty 변수에는 ((0, 1), (0, 2), (0, 3)) 다음에 ((0, 1), (0, 2), (0, 4)) 이런 식으로 3개의 벽 위치가 들어온다.

for문으로 돌면서 벽 위치를 1로 바꿔준다.

그리고 queue에 virus의 위치를 저장한다. 이 또한 for와 if의 comprehension으로 작성해주었다.

이때 BFS를 사용해야 하기에 deque로 저장했다.

 

# ---------- Function ----------
# Starting BFS   
while queue:
    x, y = queue.popleft()

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

        if 0<=nx<row and 0<=ny<col and graph[nx][ny] == 0:
            graph[nx][ny] = 2
            queue.append((nx, ny))

# Checking safe(0) area
cnt = 0
for row in graph:
    cnt += row.count(0)

result = max(cnt, result)

일반적인 BFS 함수 부분이다.

x, y를 queue 가장 왼쪽(첫 번째) 원소를 꺼내어 저장한 다음, 네 방향을 계산한다.

이때 범위를 벗어나지 않고, 갈 수 있는 상황(0)이라면,

바이러스가 퍼진 상태(2)로 바꾸고, 그 위치를 virus의 위치를 나타내는 queue에 저장한다.

 

마지막으로 cnt 변수에 각 combinations 경우에 대한 0 개수를 저장한다.

result와 비교하여 더 큰 값을 result에 저장하고 마지막으로 return한다.

이러면 함수 작성을 완료다. 코드가 길어지기는 하지만 생각보다는 풀만한 문제였다. 

 

queue = deque((x, y) for x in range(row) for y in range(col) if graph[x][y] == 2)
                              ^^^^^^^^^^
TypeError: 'list' object cannot be interpreted as an integer

그리고 에러가 떴다.

range(row)가 list라서 range() 사용이 불가능하다...?

분명 int로 받아줬는데 왜 자꾸 list 타입으로 뜨는 건지 이해할 수 없었다.

breakpoint() 함수로 확인해보니 처음은 <int>로 나오지만 두 번째부터는 <list>로 인식했다.

그럼 처음은 문제가 없지만, 한 바퀴 돌고 나서 문제이니... 코드에서 에러가 있다는 거였다.

int를 list로 바꿔주는 식의 형변환 코드는 없고... row 변수에서 문제가 생겼으니 row 변수를 확인해봤다.

 

아

마지막 코드 for row in graph에서 row 변수를 한 번 더 사용했다...

여기서 list를 덮어써서 제대로 동작하지 않은 것이었다.

변수 사용함에 있어서도 제대로 확인을 해줘야겠다.

 

# Before
cnt = 0
for row in graph:
    cnt += row.count(0)

result = max(cnt, result)

# After
cnt = 0
for line in graph:
    cnt += line.count(0)

result = max(cnt, result)

겹치는 row 변수에서 line이라는 다른 변수로 바꿔주었다.

그랬더니 정상적으로 코드가 실행되었다.

 

다행히 시간 초과가 뜨지 않고 정상적으로 완료했다.

백트래킹으로 작성하는 것도 한번 연습해봐야겠다.

 └ 알아보니 백트래킹을 이용하면 Pypy3에서만 AC가 뜨고 Python3에서는 TLE가 뜬다.

 

P.S.

전에는 이틀이나 사흘에 걸쳐 문제를 고민하고는 했는데...

어째 요즘에는 하루만에 끝나는 경우가 태반이다.

하루종일 시간을 잔뜩 갈아넣어서 하루만에 끝나는 건지... 생각이 늘어난 건지 구분이 가지 않는다.

좋은지 나쁜지 판단하는 거는 아직 시기상조일지도