[백준] 14502번: 연구소 Python (DFS, BFS) | LIM

DFS와 BFS에 관련하여 설명은 너무 많기에 내가 기억하고 싶은 것만 정리하고자 한다. 

 

DFS - Depth-First Search(깊이 우선 탐색)

즉, 깊은 부분부터 탐색하겠다는 이야기이다. 깊은 부분부터 탐색한다는 말이 사실 잘 이해가 되지 않기에 그냥 DFS는 스택을 사용한다로 외웠다. DFS는 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀함수를 이용했을 때 매우 간결하게 구현할 수 있다. 

스택은 박스 쌓기에 비유할 수 있다. 박스를 쌓다가 아래에 있는 박스를 치우기 위해서는 위에 박스부터 먼저 치워야 한다. 이러한 구조를 선입후출, 후입선출 구조라고 한다. 그냥 먼저 들어온게 나중에 나간다고 생각하면 쉽다. 왜냐하면 쌓기 때문이다. 

 

DFS가 동작하는 과정은 다음과 같다. 

1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 

 

**여기에서 방문 처리는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않도록 처리하는 것을 의미한다. 

 

BFS - Breadth First Search(너비 우선 탐색)

즉, 가까운 부분부터 탐색을 하겠다는 이야기이다. DFS가 최대한 멀리 떨어진 깊은 부분까지 탐색했다면, BFS는 그 반대이다. BFS는 큐를 이용하면 쉽게 구현할 수 있다. 큐는 선입선출 방식이다. 즉, 먼저 들어온 것이 먼저 나가는 구조이다. 

 

BFS가 동작하는 과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.

   ('모두' 라는 부분이 중요한 것 같아 강조를 했다.)

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 

 

재귀함수로 DFS를 구현하면 수행시간이 느려지는 경우가 많다. 또한, 재귀함수를 구현하려면 꼭 탈출 조건을 명시해야만 한다. (stack overflow...가 나기전에..)따라서 코딩테스트에서는 보통 DFS보다는 BFS구현이 조금 더 빠르게 동작한다. 

 

 

이 부분을 공부하고 나서 백준 14502번인 연구소 문제를 풀어보았다. 

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

14502번: 연구소

이 문제는 벽을 3개 설치하는 모든 경우의 수를 다 계산해야 한다. 나 같은 경우 0(바이러스가 퍼질 수 있는 곳, 즉 새롭게 벽을 새울 수 있는 곳)의 위치만 저장하고 그 안에서 조합을 생성했다. 그게 좀 덜 무리가 갈 것 같았다..다행히 시간초과가 나지 않았다...!

 

문제 조건이 가로, 세로 8줄로 제한이 되어 있기 때문에 모두 0이라고 가정하고 64C3을 해도 100,000을 넘지 않기 때문에 시간상의 오류는 나지 않는다. 대충 100,000,000(0이 8개)이 1초라고 생각하면 된다. 

 

내가 작성한 코드는 이러하다. 또한, 바이러스가 퍼지기 전 기존 상태를 originData로 저장했는데 이때, 그냥 originData=data로 하게 되면 메모리가 계속 참조되어 originData가 바뀔 수 있어 deepcopy를 통해 원 상태를 유지하였다. 

import itertools
import sys
import copy

input = sys.stdin.readline
data = []
n,m = map(int,input().split())
for _ in range(n):
    data.append(list(map(int,input().split())))
originData = copy.deepcopy(data)

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

# 0이 있는 곳의 위치로 벽을 세울 수 있는 곳 조합 생성
def getCombi(data):
    combiList = []
    for row in range(n):
        for i in range(m):
            if data[row][i] == 0:
                combiList.append([row,i])
    nCr = list(itertools.combinations(combiList,3))
    return nCr

# 바이러스 퍼뜨리기(재귀함수 사용)
def spreadVirus(x,y,origin):
    if origin[x][y]==2:
    	# 상하좌우 
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            # 탈출조건 명시
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if origin[nx][ny] == 0:
                origin[nx][ny] = 2
                # 재귀 수행
                spreadVirus(nx,ny,origin)
    return origin
        
# 바이러스가 퍼지고 난 후 안전 공간 카운팅
def getCount(data):
    num = 0
    for row in data:
        num += row.count(0)
    return num
    
ansList = []
real = []
for wallList in getCombi(data):
    for wall in wallList:
        data[wall[0]][wall[1]] = 1 # 위치 조합에 따라 벽 세워주기
    for i in range(n):
        for j in range(m):
            if originData[i][j] == 2: # 2라면 바이러스 퍼뜨리기
                spreadVirus(i,j,data)
    ansList.append(getCount(data)) # 안전 공간 카운팅 후 저장
    data = copy.deepcopy(originData) # 다시 원상 복귀(벽 세우기 전과 바이러스 퍼지기 전)
    continue
print(max(ansList)) # 후보 중에서 가장 큰 수 출력