알고리즘 분류
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색
- 깊이 우선 탐색
풀이
테스트 케이스 대로 숫자를 입력받으면 어떤 그래프가 나오는지 보겠습니다.
테스트 케이스 상으로는 노드 1 부터 시작하게 됩니다.
DFS: 1 - 2 - 4 - 3
BFS: 1 - 2 - 3 - 4
* 간선들의 연결이 되어 있는지 혹은 되지 않았는 것을 판단하는 것이 인접행렬을 이용하거나, 혹은 인접리스트를 이용하는 것이 좋습니다.
1) 인접 행렬
1번 꼭지점이 n번 꼭지점과 연결이 되어 있으면 1로 처리, 연결이 되어있지 않은 선은 0으로 처리
단점> 꼭지점의 갯수(Vertex)가 적을 때만 가능하다는 점. 갯수가 많아질수록 탐색 시간이 오래 걸림
2) 인접리스트
자신의 노드에서 갈 수 있는 노드를 가지고 있다고 생각하면 쉽습니다.
즉, 인접행렬에 비해 수월한점은 실제로 한 지점에서 연결되는 지점만 있기 때문에, 사실상 메모리가 차지하는 비율이 상당히 적고 그에 따라 시간복잡도 (O(n)) 가 줄어듭니다.
단, 단점이 있긴 합니다. 아까 인접리스트의 장점 A노드와 B노드가 연결되어있는지를 알고 싶은 경우에는 인접리스트에 A에는 B가 있는지 B에는 A가 있는지 파악해서 연결되어 있는 걸 확인해야 하기 때문에 직접 다 뒤적거려야하는 단점이 생깁니다.
테스트 상에서 노드를 양방향으로 연결한 간선을 표현 (인접행렬)
0 0 0 0 0
0 0 1 1 1
0 1 0 0 1
0 1 0 0 1
0 1 1 1 0
1행 2열과 2행 1열의 수가 1로 같고, .... 3행 4열 의 수가 4행 3열 과 1로 같습니다.
* 변수명
| int[][] check | 인접 행렬을 표시하기 위한 2차원 배열, DFS의 접근을 용이하게 하기 위해 전역변수로 설정 |
| boolean[] visited | 방문 여부를 나타내는 배열, 전체 노드 수만큼 할당했음 |
DFS는 스택을 사용하지 않고 재귀를 통해 구현,
BFS는 큐를 통해 구현했습니다.
JAVA
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int[][] check; // 간선 연결 상태
static int n,m; // 정점개수, 간선개수
static int start; // 시작정점
static boolean[] visited; // 방문 여부
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); //정점
m = sc.nextInt(); //간선
start = sc.nextInt(); //탐색 시작한 정점
check = new int[n+1][n+1]; // 좌표를 그대로 받아들이기 위해 +1
visited = new boolean[n+1]; // 초기값 False
// 간선 연결 상태 저장
for(int i=1; i<=m; i++) {
int x = sc.nextInt(); //1
int y = sc.nextInt(); //2
check[x][y] = check[y][x] = 1;
}
dfs(start);
visited = new boolean[n+1]; // 확인상태 초기화
System.out.println();
bfs();
}
public static void dfs(int i){
//(재귀)시작점을 변수로 받아 확인, 출력 후 다음 연결점을 찾아 시작점을 변경하여 재호출
visited[i] = true;
System.out.print(i + " ");
for(int j=1; j<=n; j++){
if(check[i][j] == 1 && visited[j] == false){
dfs(j);
}
}
}
public static void bfs(){
Queue<Integer> q = new LinkedList<Integer>();
q.offer(start); // 시작점도 큐에 넣어야 함
visited[start] = true;
System.out.print(start + " ");
// Queue가 빌 때까지 반복. 방문 정점은 확인, 출력 후 Queue에 넣어 순서대로 확인
while(!q.isEmpty()){
int tmp = q.poll();
for(int j=1; j<=n; j++){
if(check[tmp][j] == 1 && visited[j] == false){
q.offer(j);
visited[j] = true;
System.out.print(j + " ");
}
}
}
}
}DFS 와 BFS 함수 구현만 할 줄 알면 풀 수 있는 간단한 문제!!