sw마에스트로 코딩테스트를 준비하면서 그래프 탐색 문제를 풀어보았다.
오늘 푼 문제는 NumberOfIsland(섬 개수 구하기) 문제이다.
문제의 내용은 이러하다. 즉 문자로 배열이 주어지는데 1은 육지 , 0은 바다라고 주어져서 바다로 둘러 쌓인 섬의 개수를 구하는 문제이다. 
이런식으로 빨간색 줄쳐진 부분이 섬이 되는 식이다.
이러한 그래프 식 문제는 DFS,BFS 방식으로 알고리즘을 설계를 하는데 나는 DFS방식을 썼다.
DFS(깊이우선탐색)
DFS(깊이우선탐색) 이란?
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
-미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
DFS알고리즘 방식
- a 노드(시작 노드)를 방문한다.
- 방문한 노드는 방문했다고 표시한다.
- a와 인접한 노드들을 차례로 순회한다.
- a와 인접한 노드가 없다면 종료한다.
- a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
- b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.
- b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.
- 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
- 아직 방문이 안 된 정점이 없으면 종료한다.
- 있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다.
DFS를 이용해 섬 개수 구하기 구현하기
- java를 이용하여 구현 하였다.
<해결방법>
- (0,0) 좌표 값부터 탐색을한다.
- 좌표의 데이터가 '1'이면 좌표를 기준점으로 생각하고 그 값을 X로 치환한다. ->count값도 1증가 시킨다.
- 기준점을 기준으로 동서남북 4방향 탐색을 실시해서 데이터가 '1'인 좌표의 데이터는 X로 치환한다.
- 이와 같은 방법으로 주위에 '1'인 데이터가 있으면 따라가면서 '1'이 더이상 없을 때까지 탐색을 실시한다.
- 이런식으로 배열의 모든 데이터를 탐색한다.
package alogrithm_test;
import java.util.*;
public class NumberOfIsland_dfs {
public static void main(String[] args) {
char[][] grid= {
{'1','1','0','0','1'},
{'1','1','0','0','0'},
{'1','1','0','0','1'},
{'0','0','0','0','1'}
};
NumberOfIsland_dfs a = new NumberOfIsland_dfs();
a.solve(grid);
}
public int solve(char[][] grid) {
print(grid);
//1.에러처리
if(grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int count = 0 ;
//2 00이 1인것부터 들어간다.
for(int i=0;i<grid.length;i++) {
for(int j=0;j<grid[i].length;j++) {
//그래프의 원소값중 '1'인 데이터를 기준으로 잡는다.
if(grid[i][j]=='1') {
count++;
dfs(grid,i,j);
}
}
}
System.out.println("=========");
print(grid);
System.out.println("count :"+count);
return count;
}
public void dfs(char[][] grid,int i, int j) {
int m = grid.length;
int n = grid[0].length;
if(i<0 || i>=m || j<0 ||j>=n|| grid[i][j] != '1') return;
grid[i][j]='X';
//기준점을 기준으로 동서남북 사방으로 dfs탐색을 실행한다.
dfs(grid,i-1,j);
dfs(grid,i+1,j);
dfs(grid,i,j-1);
dfs(grid,i,j+1);
}
//그래프의 배열 데이터를 print한다.
public void print(char[][] grid) {
for(int i=0;i<grid.length;i++) {
for(int j=0;j<grid[i].length;j++) {
System.out.print(grid[i][j]);
}System.out.println(" ");
}
}
}이러한 방법으로 코드를 구현하였다.
처음 기준점과 그 기준점을 기준으로 주위에 있는 데이터를 차근차근 X로 치환 하는 이유는 이미 방문한 데이터는 재방문 하지 않기 위해서이다.
--이부분이 가장 중요하다고 생각되어졌다.
알고리즘 테스트에서 꾸준히 출제되고 있는 그래프 문제(DFS,BFS활용)를 꾸준히 풀어볼 생각이다. 대학교 학부과정에서 알고리즘을 배웠지만 학기가 끝나자마자 지식이 백지화된거 같다.
sw마에스트로 코딩테스트가 얼마 남지 않았지만 알고리즘 포스트도 꾸준히 써봐야겠다.
