Dfs 미로찾기 c++ - dfs milochajgi c++

깊이 우선 탐색과 너비 우선 탐색에 대해 간단하게 비교하여 정리하고자 한다.

두 알고리즘은 생각보다 알고리즘 문제 풀이에서 많이 볼 수 있고, 각각의 응용 방식을 통해 나오는 코딩 테스트 문제가 많기 때문에 참고해두는 것이 좋고, 기본적인 구현 방식은 알고 접근하는 것이 좋다. 기본적인 구현 코드는 백준 온라인 저지의 1260번 DFS와 BFS 을 구현하는 코드이다.

DFS, BFS

DFS(Depth-First Search)

Stack으로 구현할 수 있고, 함수 호출도 Stack처럼 이뤄지기 때문에 대부분 재귀 함수로 구현된 코드들이 많다. DFS는 미로 찾기로 치면, 막히는 곳까지 계속 파고 드는 Leaf-wise한 방식이다. 분기점이 나오면 길 하나를 선택하고 더 이상 진행하지 못하는 시점까지 진행한다고 보면 이해하기가 쉽다. 위에 보이는 예시처럼 일단 파고들기 시작하면 말단 노드까지 직진하는 방식이다.

Stack

void DFSStack(int num) { stack<int> st; for (int i = 0; i <= n; i++) visit[i] = false; st.push(num); while (!st.empty()) { int cur = st.top(); st.pop(); if (!visit[cur]) { cout << cur << " "; visit[cur] = true; for (int i = n; i >= 1; i--) { if (cur == i) continue; if (graph[cur][i] && !visit[i]) st.push(i); } } } }

Recursive

void DFS(int num) { cout << num << ' '; for (int i = 1; i <= n; i++) if (graph[num][i] && !visit[i]) visit[i] = 1, DFS(i); }

특이사항

1. 경로 상 노드를 모두 기억해, 적은 메모리를 사용한다.
2. 찾는 노드가 깊은 곳에 있을 때는 BFS보다 빠르다.
3. 해가 없는 상황에서, 단계가 끝날 때까지 탐색하며 이 과정에서 탐색 깊이를 지정하여 무의미한 탐색을 회피할 수 있다.
4. 해를 탐색하면 종료되기 때문에, 얻어진 해가 최단 경로라는 보장이 없다.

BFS(Breadth-First Search)

Queue로 구현할 수 있다. BFS는 미로 찾기로 치면, 야금야금 넓게 보는 방식이다. 말이 너무 추상적이라 이해하기 어려울 수 있는데, 어느 한 방향을 잡고 막 파고드는 것이 아니라 탐색 가능한 모든 방향을 한 단계씩 진행하는 Level-wise 방식이다. 위 예시에서 보면 알 수 있듯이, 트리에서 같은 레벨에 있는 모든 노드를 탐색하고 나서 다음 노드로 진행하는 방식이다.

void BFS(int start) { queue<int> q; for (int i = 0; i <= n; i++) visit[i] = false; q.push(start); visit[start] = true; while (!q.empty()) { int num = q.front(); q.pop(); cout << num << ' '; for (int i = 1; i <= n; i++) if (graph[num][i] && !visit[i]) visit[i] = true, q.push(i); } }

사람마다 다 다른데, 필자는 DFS 구현은 재귀로 하는 게 편했고, BFS 구현이 DFS 구현보다 편하다. 둘이 같이 활용될 수 있는 문제라면, 자신이 편한 것을 활용하면 되지만, 특정 몇몇의 경우에 있어서 둘 중 하나를 선택해야 하는 경우가 존재한다.

특이 사항

1. 답이 되는 경로가 여럿일 때에도 최단 경로를 보장한다.
2. 최단 경로가 존재하는 것이 보장되면 깊이와 무관하게 답을 찾아낼 수 있다.
3. 경로가 매우 많아질 경우, 많은 메모리가 필요하다.
4. 해가 존재하지 않을 때, 유한 그래프(Finite Graph)에서는 모든 그래프를 탐색한 후 종료 되며, 무한 그래프(Infinite Graph)에서는 탐색도 실패하고, 종료되지도 않는다.

유의 사항

방문 여부 체크

두 탐색 모두 방문 여부를 체크하지 않으면 무한하게 탐색하는 문제가 발생할 수 있다.

인접 행렬과 인접 리스트

구현 자체는 인접 행렬이 상대적으로 쉽다. 하지만, 활용하는 그래프의 노드의 개수가 많아지는 경우 인접 행렬로 DFS, BFS를 구현하기보다 인접 리스트를 사용하는 것이 좋다. 인접 행렬로 그래프를 구현하는 경우 정점(V)의 수가 많아질 때, O(V^2)라는 공간 복잡도가 문제가 될 수 있어, O(V+E)인 인접 리스트를 활용하는 것이 좋다.

활용하는 경우

그래프 모든 곳을 탐색하는 경우, 별 다른 제약 사항이나 어떤 특정 동작이 있는 경우가 아니면, DFS나 BFS 중 구현이 편한 걸 선택해도 무방하다. 하지만, 전처리 과정이 필요하거나 이동에 제약이 있는 경우, 백트래킹 같이 특정 알고리즘을 사용할 때는 DFS를 사용해야 하고, 가중치(weight) 없는 그래프의 최단 경로 문제는 BFS로 접근해야 한다. 이외에도 여러 가지 경우에 대해 DFS나 BFS를 선택해 활용할 때, 적절한 처리를 해줘야 한다.

[Reference]

//stackoverflow.com/questions/3332947/when-is-it-practical-to-use-depth-first-search-dfs-vs-breadth-first-search-bf

//blog.hackerearth.com/wp-content/uploads/2015/05/dfsbfs_animation_final.gifALGORITHMC++BFSDFS

//stackoverflow.com/questions/3332947/when-is-it-practical-to-use-depth-first-search-dfs-vs-breadth-first-search-bf

1. 미로찾기 (가지수 찾기)

해결방법

• 경로의 가지수이기 때문에 DFS를 활용하자
• 주의점은 check배열을 만들어서 방문한곳은 check하고 나올때는 다른 DFS가 들어갈수 있기 때문에 check배열을 해제하는것을 잊지 말자
• 첫번째 방문은 DFS들어가기전에 미리 check를 하자

코드

package inflearn.section8_dfs활용문제; import java.util.*; public class 미로탐색하기DFS { static int answer; static int n; static int arr[][]; static int ck[][]; static int dx[]={0,1,0,-1}; static int dy[]={1,0,-1,0}; public void dfs(int x,int y) { if (x==n-1&& y==n-1) { answer++; // 종료 } else { for (int i=0;i<4;i++) { int nx=x+dx[i]; int ny=y+dy[i]; if (nx>=0 && nx<=6 && ny>=0 && ny<=6 && arr[nx][ny]==0) { if (ck[nx][ny]==0) { ck[nx][ny]=1; dfs(nx,ny); ck[nx][ny]=0; // 갔던곳 다시 풀어줌 } } } } } public static void main(String[] args) { Scanner scan=new Scanner(System.in); n=7; arr=new int[n][n]; ck=new int[n][n]; for (int i=0;i<n;i++) { for (int j=0;j<n;j++) { arr[i][j]=scan.nextInt(); } } 미로탐색하기DFS m1=new 미로탐색하기DFS(); ck[0][0]=1; m1.dfs(0,0); System.out.println(answer); } }

2. 미로찾기 최단거리로 이동하는 경우

해결방법

• 최단거리는 BFS로 문제를 풀자
• 이때 주의점은 큐를 사용하는데 안에 매개변수로는 Point class를 만들어서 x,y를 넣게 만들자
• 또한 거리를 저장해야 되기 때문에 DIS[x][y] (메모제이션)를 만들어서 해결해야 한다. DIS[nx][ny]=DIS[x][y]+1 // 현재 위치에서 +1 씩 증가한다.
• Queue를 다 돌은 후에는 마지막 위치 (6,6)을 출력해주자.

코드

package inflearn.section8_dfs활용문제; import java.util.*; public class 미로탐색하기BFS { static int ck[][]; // 굳이 필요할까?! 필요하네, 이유는 더이상 못가기 위해서 갔던길을 static int arr[][]; static int n; static int answer=0; static int dx[]={0,1,0,-1}; static int dy[]={1,0,-1,0}; // dis 추가 static int dis[][]; class Point { int x; int y; Point(int x,int y) { this.x=x; this.y=y; } } public void bfs(int x,int y) { Queue<Point> queue=new LinkedList<>(); Point point=new Point(x,y); queue.add(point); while(!queue.isEmpty()) { int size= queue.size(); // 큐사이즈 만큼 돌음 for (int i=0;i<size;i++) { Point pq=queue.poll(); int xx=pq.x; int yy=pq.y; for (int j=0;j<4;j++) { int nx=xx+dx[j]; int ny=yy+dy[j]; if (nx>=0 && nx<=6 && ny>=0 && ny<=6 && arr[nx][ny]==0) { if (ck[nx][ny]==0) { // 이것때문에 큐에 더 못더함 ck[nx][ny]=1; Point pp=new Point(nx,ny); queue.add(pp); dis[nx][ny]=dis[xx][yy]+1; } } } } // answer++; } } public static void main(String[] args) { Scanner scan=new Scanner(System.in); arr=new int[7][7]; ck=new int[7][7]; for (int i=0;i<7;i++) { for (int j=0;j<7;j++) { arr[i][j]=scan.nextInt(); } } dis=new int[7][7]; ck[0][0]=1; 미로탐색하기BFS m1=new 미로탐색하기BFS(); m1.bfs(0,0); // System.out.println(answer); for (int i=0;i<7;i++) { for (int j=0;j<7;j++) { // dis[i][j]; System.out.print(dis[i][j]+" "); } System.out.println(); } } }

3. 토마토

해결방법

• 동시 진행하여야 됨으로 초기 큐에 익은토마토를 집어넣는것이 핵심
• 이 경우는 2개의 좌표가 큐에 들어감
• DIS[x][y]는 날짜를 기록하는 메모제이션, 초기값은 -1과 1만 있을경우에 DIS를 세팅해줌
• 그리고 bfs에서 arr[nx][ny]==0이고 dis[x][y]>=1보다 큰 경우에만 dis[nx][ny]=dis[x][y]+1로 신규 날짜를 갱신

코드

package inflearn.section8_dfs활용문제; import java.util.*; public class 토마토 { static int n; static int m; static int arr[][]; static int dis[][]; static Queue<Point>queue; static int dx[]={0,1,0,-1}; static int dy[]={1,0,-1,0}; static class Point { int x; int y; Point(int x,int y) { this.x=x; this.y=y; } } void bfs() { // 토마토 진행하기 // 큐에 이미 담아있음 while (!queue.isEmpty()) { int size= queue.size(); for (int i=0;i<size;i++) { // 큐 한개 꺼냄 Point k=queue.poll(); for (int j=0;j<4;j++) { int nx=k.x+dx[j]; int ny=k.y+dy[j]; // m이 행 4 n이 열 6 // System.out.println("nx:"+nx); // System.out.println("ny"+ny); if (nx>=0 && nx<n && ny>=0 && ny<m) { if (arr[nx][ny]==0) { // DIS에 일수 기록하기 if (dis[nx][ny]>=0) { // -1을 제외하기 위해서 dis[nx][ny]=dis[k.x][k.y]+1; } // 갔던곳은 1로 처리 arr[nx][ny]=1; Point p=new Point(nx,ny); queue.add(p); // queue에 신 좌표 넣기 } } } } } } public static void main(String[] args) { Scanner scan=new Scanner(System.in); m=scan.nextInt(); n=scan.nextInt(); arr=new int[n][m]; for (int i=0;i<n;i++) { for (int j=0;j<m;j++) { arr[i][j]=scan.nextInt(); } } queue=new LinkedList<>(); // DIS 초기값 세팅하기 dis=new int[n][m]; for (int i=0;i<n;i++) { for (int j=0;j<m;j++) { if (arr[i][j]==-1 || arr[i][j]==1) { dis[i][j]=arr[i][j]; } } } // 다 익은 토마토인지 미리 검사하기 boolean check=false; for (int i=0;i<n;i++) { for (int j=0;j<m;j++) { if (arr[i][j]==0) { check=true; } } } // 다 안익은 토마토가 있다. if (!check) { System.out.println(1); } else { // 큐에 익은 토마토 넣기 for (int i=0;i<n;i++) { for (int j=0;j<m;j++) { if (arr[i][j]==1) { Point point=new Point(i,j); queue.add(point); } } } // BFS진행하기 토마토 m1=new 토마토(); m1.bfs(); // 익지못한 토마토가 존재한다. -> -1 return boolean check2=false; int maxValue=Integer.MIN_VALUE; for (int i=0;i<n;i++) { for (int j=0;j<m;j++) { // System.out.print(dis[i][j]+" "); if (dis[i][j]==0) { check2=true; } if (dis[i][j]>=1) { if (maxValue<dis[i][j]) { maxValue=dis[i][j]; } } } } if (check2) { System.out.println(-1); } else { System.out.println(maxValue-1); } } } }