그래프 이해
알고리즘: 그래프(Graph)의 탐색과 메소드 이해&구현
그래프와 트리의 차이 사이클의 유무이다. 노드를 출발해 간선의 방향으로 따라 출발한 노드로 다시 돌아올...
blog.naver.com
문제 예시: 백준 2178 번
배열 안에서 경로의 최소값을 구하는 문제입니다.
어떤 방식을 생각할 수 있을까요?
1. DP (Dynamic Programming)
연속된 무언가의 최소값이나 최대값을 구할 때 가장 먼저 떠오르는 키워드 중 하나는 DP일 것입니다.
여기서는 다루지 않고 넘어가겠습니다!
2. DFS (깊이 우선 탐색) 방문정점 구하기
그래프를 배우기 전에는 2차원 배열은 단순히 2차원에 값을 저장하는 도구입니다.
하지만 그래프를 학습하면서 DFS와 BFS 탐색법을 배우고 그래프의 연결관계를 2차원 배열 안에 저장할 수 있다는 것을 학습합니다.
대부분의 탐색에서의 핵심은 이미 방문했다는 기록을 남기는 것입니다. 이를 위해 방문을 기록하는 배열을 생성합니다.
boolean check = new boolean[N][N]; //탐색을 하는 순간 true로 변경해 방문을 기록하는 배열
// ex) 백트래킹, DFS, BFS
DFS는 재귀호출을 이용하여 다음 조건을 만족하는 곳을 연쇄적으로 탐색합니다.
1) 이미 방문한 곳은 제외한다
2) 이전에 탐색한 곳과 연결되어있다
import java.util.*;
public class Main {
static boolean[][] check; // 방문을 기록하는 배열
static boolean[][] arr; // 그래프의 연결관계를 기록하는 배열
static int N; //배열의 크기
static int count=0; //방문 정점의 개수
public static void dfs(int i,int j) { //DFS 메소드
if(i<0 || i>=N || j<0 || j>=N || !arr[i][j] || check[i][j] ) {
//배열 밖을 벗어나버리면 BoundException 오류가 발생하기 때문에 앞에 먼저 조건으로 걸러줍니다
//이미 방문한 곳이거나(check[][] 배열이 true)
//연결관계가 존재하지 않는다면 (arr[][] 배열이 false) 탐색을 중단합니다 (=return)
return;
}
check[i][j]=true; //위 조건을 회피했다면 탐색해야하므로 방문 표시
count++; //방문 표시를 함과 동시에 방문 정점 카운트
dfs(i+1,j); //상 하 좌 우 재귀 메소드 호출
dfs(i-1,j);
dfs(i,j+1);
dfs(i,j-1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
N = sc.nextInt();
arr=new boolean[N][N];
check=new boolean[N][N];
int[] record= new int[N*N];
int count2=0;
for(int i=0;i<N;i++) { //연결관계 기록
String s = sc.next();
for(int j=0;j<N;j++) {
if(s.charAt(j)=='1') {
arr[i][j]=true;
}
}
}
//본격적인 탐색 시작
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
//연결관계 존재, 방문은 하지 않는 곳에서 호출
if(arr[i][j] && !check[i][j]) {
dfs(i,j); //이 좌표 주변 원소들도 연쇄적으로 방문되면서 방문 표시
record[count2]=count;
count2++;
count=0;
}
}
}
//문제 조건에 맞는 출력 부분이므로 신경X
Arrays.sort(record);
System.out.println(count2);
for(int i=0;i<N*N;i++) {
if(record[i]!=0) {
System.out.println(record[i]);
}
}
}}
3. DFS (깊이 우선 탐색) 최소 경로 구하기
위의 방식대로 경로의 최소 또한 구할 수 있지 않을까? 생각할 수 있습니다.
과연 DFS로 이 포스팅의 맨 처음 제시된 문제를 풀이할 수 있을까요?
DFS를 사용해 시작점에서 출발해 연쇄적으로 재귀호출해 도착점까지 도달하는 모든 방법을 구하고 그 중 최소값을 출력하면 될 것입니다.
import java.util.*;
public class Main {
static boolean[][] arr; //연결관계 기록하는 배열
static boolean[][] check; //방문 기록 배열
static int M,N; //판의 크기
static int min=10000; // 앞으로 갱신될 최소경로 기록
public static void minTrack(int i,int j,int count) {
if(i<0 || i>=M || j<0 || j>=N || !arr[i][j] || check[i][j]) {
return;
}
count=count+1; //위 조건을 뚫고 통과했다면 연결&방문X인 곳이므로 1추가합니다
if(i==0 && j==0) {
min=Math.min(min, count);
//만약 처음 위치로 도달했다면 도착한 것이므로 지금까지의 경로와 최소값을 비교해 갱신합니다
}
//도달하지 않았다면 방문 체크를 해주고 다시 상 하 좌 우 메소드를 재귀호출합니다
check[i][j]=true;
minTrack(i+1,j,count);
minTrack(i-1,j,count);
minTrack(i,j+1,count);
minTrack(i,j-1,count);
check[i][j]=false;
//방문해제를 해주어 재활용가능하도록 만듭니다
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
M=sc.nextInt();
N=sc.nextInt();
arr=new boolean[M][N];
check=new boolean[M][N];
for(int i=0;i<M;i++) {
String s = sc.next();
for(int j=0;j<N;j++) {
if(s.charAt(j)=='1') {
arr[i][j]=true;
}
}
}
minTrack(M-1,N-1,0);
//도착점에서 호출해 시작점에 도달합니다
System.out.println(min);
}}
배열의 크기가 작다면 이 방법으로 충분히 값을 구할 수 있습니다. 하지만 배열이 매우 크다면???
경로도 엄청 많아질 것이고 재귀호출의 수도 기하급수적으로 증가하기 때문에 시간초과가 발생합니다.
즉 순수 DFS 탐색으로는 최소경로를 구하는데 한계를 맞이합니다.
다른 방법, BFS를 통한 풀이가 필요합니다.
4. BFS (너비 우선 탐색) 원리
BFS 탐색의 핵심은 큐(Queue)를 이용하는 것이었습니다. 방법은 상위노드를 일단 집어넣고 빼면서 그 하위 노드를 집어넣습니다.
0을 집어넣으면: { 0 }
0을 빼면서 동시에 0과 연결된 1과 2를 집어넣기: { 2, 1 } //큐이기 때문에 1이 출구인 오른쪽에 가깝습니다
1을 빼면서 동시에 1과 연결된 2과 4를 집어넣기: { 4, 3, 2 }
2를 빼면서 동시에 2와 연결된 5와 6을 집어넣기: { 6, 5, 4, 3 }
이런 방식을 통해 상위 노드부터 그래프를 탐색할 수 있었습니다.
5. BFS (너비 우선 탐색) 을 이용해 최소 경로 구하기
BFS를 이용하면 DFS처럼 굳이 모든 경로의 경우의 수를 구하지 않아도 됩니다.
|
1
|
1
|
1
|
|
1
|
0
|
1
|
|
1
|
1
|
1
|
위의 최소 경로를 DFS로 구한다면 빨간색 시작점을 제외하고 총 8번의 호출이 발생합니다.
메소드에 포함된 코드 길이까지 포함하면 꽤나 긴 문장을 지납니다.
하지만 BFS로 구한다면 간단하게 누적합을 구하는 방식으로 구할 수 있습니다.
|
1
|
2
|
3
|
|
2
|
0
|
4
|
|
3
|
4
|
5
|
현재 위치에서 상하좌우의 좌표를 알려줘야하는데 반복문을 사용해 호출할 수 있습니다
int dx = { 1, -1, 0, 0 };
int dy = { 0, 0, 1, -1 };이 배열을 for문을 이용해 index를 맞추어 호출하면 상하좌우를 편리하게 완성할 수 있습니다.
for(int i=0;i<4;i++){
int x = dx[i];
int y = dy[i];
}이후 사고하기 가장 어려운 부분은 스택에 집어넣을 정보의 형태입니다.
바로 x,y 좌표의 정보를 모두 스택 안에 기록해주어야 한다는 것입니다.
이 때문에 성향에 따라 여러 방식을 사용하는데 크게 두 가지 방법이 있었습니다.
1) 두 개의 스택을 만들고 각각 x 좌표와 y좌표의 정보를 집어넣는다
2) 하나의 스택 안에 <객체> 형태로 x,y 값을 저장한다2번 방식을 중점으로 다루겠습니다.
배열의 형태, 즉 객체의 형태로 집어넣을 때 new 명령어를 사용해 큐 안에 넣어줍니다(임시로 생성하기 때문에)
또한 위의 상하좌우 좌표 개념과 합쳐져 기본틀은 아래와 같아집니다.
public static void bfs(int x, int y) {
Queue<int[]> queue = new LinkedList<int[]>();
check[0][0]=true;
queue.add(new int[] {x,y}); //임시 객체를 넣어줍니다. 초기값은 0,0입니다
while(!queue.isEmpty()) {
int[] now = queue.poll(); //객체를 빼주고
int nowX = now[0]; //분해해서 다시 변수에 저장합니다
int nowY = now[1];
for(int i=0;i<4;i++) {
int nextX = nowX + dx[i];
int nextY = nowY + dy[i];
if(nextX<0 || nextY<0 || nextX>=M || nextY>=N || arr[nextX][nextY]==0 || check[nextX][nextY]) {
continue;
}
queue.add(new int[] {nextX,nextY}); //조건에 맞다면 큐에 넣습니다
check[nextX][nextY]=true; //방문 체크합니다
arr[nextX][nextY]=arr[nowX][nowY]+1;
}
}
}1) 조건에 맞지 않는 값들은 continue를 통해 걸러집니다
2) 방문체크합니다
3) 다음 항에 현재항의 숫자+1을 합니다
arr[nextX][nextY]=arr[nowX][nowY]+1;여기서 단순히 현재항에 1을 더하고 도착점에 값을 출력하면 최소값이 구해지는 것인가 생각할 수 있습니다.
경로가 엄청 많이 있을텐데 다른 경로에서 생긴 값이 덮어씌워지면서 오류가 발생할 수 있는 가능성을 생각할 수 있기 때문입니다.
하지만 그렇게 되지 않습니다. BFS 의 탐색 방식은 수평적임을 명심해야 합니다.
A B C 루트가 있다고 해도 가장 짧은 루트가 결국 그 위치를 먼저 도달해 방문 체크를 하며 그 값이 곧 최소값이 됩니다.
이후에 도달한다고 해도 이미 방문체크가 되어있어서 값이 변경되는 일이 없습니다. 곧, 최소값을 구할 수 있는 이유가 됩니다.
전체코드입니다!
import java.util.*;
public class Main {
static int[][] arr;
static boolean[][] check;
static int M,N;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,1,-1};
public static void bfs(int x, int y) {
Queue<int[]> queue = new LinkedList<int[]>();
check[0][0]=true;
queue.add(new int[] {x,y});
while(!queue.isEmpty()) {
int[] now = queue.poll();
int nowX = now[0];
int nowY = now[1];
for(int i=0;i<4;i++) {
int nextX = nowX + dx[i];
int nextY = nowY + dy[i];
if(nextX<0 || nextY<0 || nextX>=M || nextY>=N || arr[nextX][nextY]==0 || check[nextX][nextY]) {
continue;
}
queue.add(new int[] {nextX,nextY});
arr[nextX][nextY]=arr[nowX][nowY]+1;
check[nextX][nextY]=true;
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
M=sc.nextInt();
N=sc.nextInt();
arr=new int[M][N];
check=new boolean[M][N];
for(int i=0;i<M;i++) {
String s = sc.next();
for(int j=0;j<N;j++) {
if(s.charAt(j)=='1') {
arr[i][j]=1;
}
}
}
bfs(0,0);
System.out.println(arr[M-1][N-1]);
}}
'Study > 알고리즘' 카테고리의 다른 글
| 알고리즘: 그래프(Graph)의 탐색과 메소드 이해&구현 (0) | 2022.01.04 |
|---|---|
| 백준: 최대공약수(GCD)와 최소공배수(LCM) 구하는 메소드 (나머지 연산) (0) | 2021.12.03 |
| 백트래킹(Backtracking)의 개념과 DFS로의 확장, N-Queen (0) | 2021.11.17 |
| 알고리즘: 정렬 - 삽입 정렬, 버블 정렬, 병합 정렬, 선택 정렬, 퀵 정렬, 힙 정렬, 카운팅(계수) 정렬 (0) | 2021.11.04 |
| 그리디 알고리즘(Greedy Algorithm)의 이해와 적용 (0) | 2021.11.02 |