해당 문제는 깊이 우선 탐색이나 너비 우선 탐색을 사용할 수 있는지 여부를 묻는 문제이다.
깊이 우선 탐색은 "재귀"를 사용하여 깊이 방문하는 알고리즘이고, 너비 우선 탐색은 "큐(Queue)"를 사용하여 두루두루 방문하는 방법이다.
위와 같이 탐색할 대상(보통 각각의 요소가 연결되어 있거나 인접한 것으로 구성된 집합체)이 존재할 때,
BFS는 위와 같이 위에서 아래로 "가로"로 탐색을 진행하는 방법이다.
from collections import deque
def bfs(x,y):
que = deque()
que.append((x,y))
# 장애물 크기 담을 변수 준비
count = 0
while que:
# que 에서 x,y 값을 하나 빼온다.
x, y = que.popleft()
# 만약 x,y가 격자 안에 존재하는 값이고, 장애물이 존재할 경우
if (0 <= x < N) and (0 <= y < N) and (map[x][y]==1):
count += 1
map[x][y] = 0
for i in range(len(dx)):
new_x = x + dx[i]
new_y = y + dy[i]
if (0 <= new_x < N) and (0 <= new_y < N) and (map[new_x][new_y]==1):
que.append((new_x,new_y))
return count
BFS를 실제 예시를 통해 설명을 해보자면,
1. BFS의 가장 독특한 특성은 FIFO(First In First Out - 데이터가 들어간 선착순으로 뽑아져 나오는 데이터 구조)의 특성을 가진 "큐 (Queue)" 데이터 구조를 사용한다.
2. BFS는 이러한 큐에 다음 탐색 요소들을 하나하나 차곡차곡 담으며, 큐 안에 데이터가 없어질 때 까지 값을 뽑아서 지속해서 탐색을 돌리는 특성을 지녔다.
3. 그리고 큐에 데이터를 담을 때 어떠한 "특정한 조건"이 존재한다.
위의 특성을 통해 너비 우선 탐색이라는 알고리즘을 실현시킬 수가 있다. 여기서 유의할 점은 큐가 돌아가는 while 안에서 계속 큐에 데이터가 들어가는데, 이 데이터가 들어가는 과정을 어떠한 특정한 조건을 통해 필터링을 해주는 것이 중요하다. 그렇지 않으면 데이터가 계속 들어가 코드가 엉망이 될 수 있기 때문이다.
그리고 보통 이 특정한 조건을 어떻게 정해주느냐가 결국 BFS 관련 알고리즘 문제를 푸는 관건이 되곤 한다.
위 코드에선 해당 조건이 "if (0 <= x < N) and (0 <= y < N) and (map[x][y]==1):"로 나타나 있다.
DFS는 위와 같이 위에서 아래로 "세로"로 탐색을 진행하는 방법이다.
def dfs(x, y):
global count
if (0 <= x < N) and (0 <= y < N) and (map[x][y]==1):
count += 1
map[x][y] = 0
for i in range(len(dx)):
next_x = x + dx[i]
next_y = y + dy[i]
# 재귀로 다음 깊이로 넘어간다.
dfs(next_x, next_y)
return True
return False
DFS 또한 실제 예시를 통해 설명하자면,
1. DFS는 "함수의 재귀"를 통해 진행이 된다는 가장 큰 특징을 지니며,
2. DFS 알고리즘 안에는 "코드를 종료시키는 특별한 조건"이 존재한다.
함수의 재귀란 함수를 돌리는 과정에서 함수를 또 돌리는 방법을 말한다. 재귀는 효율적이긴 하지만 잘못하면 이 함수가 끝나지 않아 무한으로 돌아가는 현상이 나타난다는 점이다. 그렇기에 재귀를 표현하는데 있어서 가장 중요한 점은 "함수를 돌리는 특정한 조건", 또는 다른 말로 표현하자면 "함수를 끝내는 특정한 조건"을 꼭 넣어주어야만 한다. 그리고 이 특정한 조건이 곧 DFS 관련 알고리즘 문제를 푸는 중요한 관건 요소가 된다.
위의 코드에서는 "함수를 돌리는 특정한 조건"을 설정해주었고, 이는 "if (0 <= x < N) and (0 <= y < N) and (map[x][y]==1):" 라는 코드로 설정할 수 있었다. 실제로 이 특정한 조건은 이 문제에서 가장 중심이 되는 부분이다.
코드
1. BFS (너비 우선 탐색 - Breadth-First Search)
import sys
from collections import deque
# 지도 크기 N
N = int(input())
# 지도 N개의 자료
map = [list(map(int, input())) for _ in range(N)]
# 장애물 갯수 담을 리스트
result = []
# 이동
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def bfs(x,y):
que = deque()
que.append((x,y))
# 장애물 크기 담을 변수 준비
count = 0
while que:
# que 에서 x,y 값을 하나 빼온다.
x, y = que.popleft()
# 만약 x,y가 격자 안에 존재하는 값이고, 장애물이 존재할 경우
if (0 <= x < N) and (0 <= y < N) and (map[x][y]==1):
# 장애물 갯수 추가
count += 1
# 그리고 지도에 1이었던 것 0으로 표시 (다음에 절대 탐색 안하게 됨)
map[x][y] = 0
for i in range(len(dx)):
new_x = x + dx[i]
new_y = y + dy[i]
if (0 <= new_x < N) and (0 <= new_y < N) and (map[new_x][new_y]==1):
que.append((new_x,new_y))
return count
for x in range(N):
for y in range(N):
obs_size = bfs(x,y)
if (obs_size != 0):
result.append(obs_size)
sorted_result = sorted(result)
print(len(sorted_result))
for i in sorted_result:
print(i)
2. DFS (깊이 우선 탐색 - Depth-First Search)
import sys
N = int(input())
map = [list(map(int, input())) for _ in range(N)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
count = 0
result = []
def dfs(x, y):
global count
if (0 <= x < N) and (0 <= y < N) and (map[x][y]==1):
# 장애물 갯수 추가
count += 1
# 그리고 지도에 해당 위치를 0으로 표시함 (다음에 절대 탐색 안하게 됨)
map[x][y] = 0
for i in range(len(dx)):
next_x = x + dx[i]
next_y = y + dy[i]
# 재귀로 다음 깊이로 넘어간다.
dfs(next_x, next_y)
return True
return False
for x in range(N):
for y in range(N):
count = 0
if (dfs(x,y)):
result.append(count)
sorted_result = sorted(result)
print(len(sorted_result))
for i in sorted_result:
print(i)
결과
DFS와 BFS 알고리즘 모두 정답이 나왔다.
이 문제를 풀 때 주로 실수를 했던 점은
def dfs(x, y):
global count
if (0 <= x < N) and (0 <= y < N) and (map[x][y]==1):
# 장애물 갯수 추가
count += 1
# 그리고 지도에 해당 위치를 0으로 표시함 (다음에 절대 탐색 안하게 됨)
map[x][y] = 0
for i in range(len(dx)):
next_x = x + dx[i]
next_y = y + dy[i]
# 재귀로 다음 깊이로 넘어간다.
dfs(next_x, next_y)
return True
return False
위치를 이동할 때, next_x = x+dx[i]로 표시를 해야 하는데 실수로 x = x + dx[i]로 표시해서 얼렁뚱땅한 방향으로 탐색을 진행하도록 코드를 설계했던 것이다. 이동을 할 때 하나의 축 "x, y"를 확실히 잡아주는 게 이 문제를 푸는데 꽤나 중요한 요소인 것 같다.
그리고 다른 작은 하나의 실수는 변수를 제대로 보지 못하고 잘못 적은 부분이었던 것 같다. (예를 들어 dfs(next_x, next_y)를 써야 하는데 dfs(x,y) 라고 쓰는 실수를 저질러 버렸다.)
