백준 26170을 시도했다 뭔가 이상함을 느끼며 실패했고 백준 25418번을 푸는데 있어 이상함이 정확하다 판단했고 구체적으로 DFS, BFS의 구현에 대해 집고 넘어가기 위해 글을 작성한다
이상함의 이유는 2차원 배열 형태에서 거리를 탐색하는데 있어 BFS와 DFS의 차이점을 구분짓지 않고 DFS로 풀었기 때문이었다
DFS와 BFS의 가장 큰 차이점으로 QUEUE, STACK 형태로 알고 있었고 코드를 구현하는데 있어 QUEUE와 STACK의 자료구조를 알고있는 것 만으로도 충분하다 생각했지만 얕은 생각이었고 프로그램의 구현 방식으로도 QUEUE와 STACK처럼 이용할 수 있다는 것을 알 수 있었다
DFS 코드
python
- 재귀를 이용한 DFS 코드
arr = [[0] * 5 for i in range(5)]
check = [[False] * 5 for i in range(5)]
def check_dist(x,y,dist):
global arr
if (0 <= x and x < len(arr)) and (0 <= y and y < len(arr)):
if not check[x][y]:
arr[x][y] = dist
check[x][y] = True
dist += 1
check_dist(x+1, y, dist)
check_dist(x, y+1, dist)
check_dist(x-1, y, dist)
check_dist(x, y-1, dist)
else:
return
check_dist(2,2,0)
for i in arr:
print(i)출력
설명
- 방문 여부, index 길이 등의 조건에 맞춰 재귀를 이용해 DFS를 구현했고 이 때 상하좌우를(하,우,상,좌) 순으로 진행했으며 DFS는 일정한 방향성을 갖춰 거리를 잰다
- 방문 여부의 필요성을 느끼지 못했지만 이 부분은 정말 간단하게 방문 여부 말고는 코드 내에서 재귀를 멈출 수 있는 경우가 없다는 것
- 상하좌우를 반복하며 계속해서 2차원 배열 안에 머무르는 재귀문이 존재
- 재귀는 컴퓨터에서 stack과 같은 구조로 운영되기 때문에 재귀문(=stack)을 이용해 DFS 구현
Java, Stack 이용
import java.util.*;
public class Main {
public static void main(String[] args){
Stack<Integer> stack = new Stack<>();
boolean[] visited;
int[][] graph = {
{}
,{2, 3, 8}
,{1, 7}
,{1, 4, 5}
,{3, 5}
,{3, 4}
,{7}
,{2, 6, 8}
,{1, 7}
};
visited = new boolean[graph.length];
stack.push(1);
System.out.print(1+" ");
visited[1] = true;
while(stack.size() > 0) {
boolean check = false;
int node = stack.get(stack.size()-1);
for(int i = 0; i<graph[node].length; i++){
if (!visited[graph[node][i]]) {
stack.push(graph[node][i]);
System.out.print(graph[node][i]+" ");
visited[graph[node][i]] = true;
check = true;
break;
}
}
if (!check) {
stack.pop();
}
}
}
}출력
1 2 7 6 8 3 4 5
해설
Stack을 사용한 경우이며 처음 시작 노드를 넣고 시작 노드의 Graph에서 방문하지 않은 노드가 있는 경우 스택에 추가, 방문하지 않은 노드가 없는 경우는 pop() 이용해 진행
깊이가 우선이기에 방문하지 않은 노드가 있는 경우 추가하고 for 반복문을 이탈하며 방문하지 않은 노드가 있고 없고는 스택에 방문하지 않은 경우는 check 변수를 true로 바꿔 확인
Java, 재귀 이용
Stack 이용한 경우와 같은 Graph
import java.util.*;
public class Main {
static void dfs(int[][] graph, int node, boolean[] visited){
visited[node] = true;
System.out.print(node + " ");
for(int i = 0; i<graph[node].length; i++){
if(!visited[graph[node][i]]){
dfs(graph, graph[node][i], visited);
}
}
}
public static void main(String[] args){
boolean[] visited;
int[][] graph = {
{}
,{2, 3, 8}
,{1, 7}
,{1, 4, 5}
,{3, 5}
,{3, 4}
,{7}
,{2, 6, 8}
,{1, 7}
};
visited = new boolean[graph.length];
dfs(graph, 1, visited);
}
}출력
1 2 7 6 8 3 4 5
설명
우선 특징은 Stack을 이용한 경우보다 굉장히 간결하다
재귀는 DFS 이론 자체처럼 기준 노드에서 방문하지 않은 노드가 존재하는 경우 DFS 재귀 호출하는 방식으로 진행된다
구체적으로
1=> 2 => 7 => 6과정을 처음으로 진행하고
6노드에서 더 이상 방문하지 않은 노드가 없기에 이 전 상황으로 돌아가
7노드에서 for6, 8형태에서6다음8번 노드를 방문해1=> 2 => 7 => 8로 진행하며
8번 기준으로 모두 방문했기에2,
마찬가지로2노드도 모두 방문했기에
1번 노드로 돌아가1 => 3 => 4 => 5과정을 거친다
재귀 = 반복문의 중첩이라 생각하면 이해하기 쉬울 것 같다
for
for
for재귀의 경우 프로그램 종료를 위해 종료 조건이 의무적으로 필요한데 for문을 이용해 재귀를 선언했기에 for문 종료 = 종료로 따로 정의해주지 않아도 된다
백트랙킹 - BackTracking
위에 진행했던 기본적인 DFS의 경우 노드들의 조건을 따지는 것이 아닌 모든 경우의 수를 탐색하는 것
단순히 for문이 종료되며 재귀가 종료되는 방식이다
백트래킹의 경우는 한정 조건이란 것을 가지며 한정 조건을 만족하는 모든 경우의 수를 탐색하는데 목적이 있다
한정 조건을 따지고 만족하지 않은 경우 이전 상황으로 복귀하며 탐색하는 구조
프로그램 구조는 재귀를 이용해 진행했을 경우 재귀 함수 내부의 재귀 종료 조건, 한정 조건 두 가지를 이용해 문제에 상황에 맞게 진행하면 된다
코드는 해당 문제를 참고하면 될 것 (https://velog.io/@sung-ik-je/%EB%B0%B1%EC%A4%80-26169)
백트래킹을 사용하는데 있어 유의해야 될 점은 한정 조건을 이용해 경로를 설정하다 현 경로가 올바르지 않은 경우 다시 복귀하게 되는데 이 때, 즉 dfs 탐색이 끝난 후 한정 조건을 다시 수정해야한다
- 예를 들어 1번 노드를 지나 2번에 위치했다고 가정 했을 때 2번 노드 입장에서 1번은 다시 돌아갈 수 없는 입장이기에 2번 노드로 이동하면서 1번 노드를
한정 조건을 만족하지 않도록 수정한다 - 이후 2번 노드에 위치했을 때 이 경로가 틀렸다는 것을 인지했을 경우 다른 경우의 수를 탐색에 영향을 주지 않기 위해 1번 노드를
한정 조건에 만족하게 다시 초기화 시킨다
DFS와의 차이 핵심
DFS의 경우 완전 탐색이라 생각하면 된다
때문에 조건을 계속해서 고려하기 때문에 계속해서 함수를 호출하며 가지치기 필요 X
단순히 함수를 호출하며 탐색하기만 하면 된다
하지만 백트래킹의 경우 가지치기가 필요
즉, 현재 경로가 틀렸다고 생각한 경우 이전 경로로 복귀해 다른 가지로 작업이 필요하기 때문에 방문 표시 유무를 핸들링 할 필요 존재
ex) 순열, 조합의 경우 재귀, 백트래킹 2개의 구현 방법이 있는데 백트래킹을 사용한 경우는 가지치기를 목적으로 방문 표시를 핸들링 할 필요가 있다
BFS
Python
score = [[0 for _ in range(5)] for _ in range(5)]
visit = [[False for _ in range(5)] for _ in range(5)]
q = deque()
def bfs(x,y,z):
if (0 <= x and x < 5) and (0 <= y and y < 5):
if visit[x][y] == False:
score[x][y] = z
visit[x][y] = True
q.append([x+1, y, z+1])
q.append([x, y+1, z+1])
q.append([x-1, y, z+1])
q.append([x, y-1, z+1])
while len(q) != 0:
x2, y2, z2 = q.popleft()
bfs(x2, y2, z2)
else:
return
bfs(2,2,0)
for i in score:
print(i)출력
설명
- 처음 시작점을 queue에 넣고 함수에는 거리 주입, 방문 체크, 상하좌우 q에 추가해 q에 맨 앞에 위치한 지점을 뽑으며 진행
- DFS와의 가장 큰 차이점은 DFS는 stack = 맨 마지막 지점을 뽑아 사용하지만 BFS는 queue = 맨 앞 지점을 뽑아 사용
- 때문에 DFS는
재귀로 프로그램 이어가지만 BFS의 경우는queue 돌리고 재귀로 문제 해결
- 때문에 DFS는
Java
DFS graph와 동일
import java.util.*;
public class Main {
public static void main(String[] args){
boolean[] visited;
int[][] graph = {
{}
,{2, 3, 8}
,{1, 7}
,{1, 4, 5}
,{3, 5}
,{3, 4}
,{7}
,{2, 6, 8}
,{1, 7}
};
visited = new boolean[graph.length];
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
visited[1] = true;
while(queue.size() > 0){
int node = queue.poll();
System.out.print(node + " ");
for(int i = 0; i<graph[node].length; i++){
if(!visited[graph[node][i]]){
queue.add(graph[node][i]);
visited[graph[node][i]] = true;
}
}
}
}
}출력
1 2 3 8 7 4 5 6
설명
- 처음 큐에 시작 노드를 집어 넣고 시작
- 큐의 맨 앞 노드를 꺼내 graph 상에 방문하지 않은 노드들 모두 큐에 추가
1, 2번 반복
