[백준] 2178번 미로탐색

DFS ->스택이용

BFS ->큐 이용

 

 

DFS,BFS 응용/활용 문제

단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 다 가능

• 경로의 특징을 저장해둬야 하는 문제 예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못함)

• 최단거리 구해야 하는 문제 + 간선의 가중치 1
  미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리하다.
  왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문.

이밖에도

1. 검색 대상 그래프가 정말 크다면 DFS를 고려
2. 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS를 고려하는 것이 좋다.

 

출처 :https://velog.io/@tsi0521/%EB%AF%B8%EB%A1%9C-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-DFS-%EC%99%80-BFS-%EB%B9%84%EA%B5%90

package days01;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
 static int N,M,cnt=0;
 static int visited[][], mat[][];
public static void main(String[] args) {
	Scanner scan=new Scanner(System.in);
	N=scan.nextInt();
	M=scan.nextInt();
	visited=new int[N][M]; //방문했던 곳인지 체크 
	mat=new int[N][M]; //입력받은 1010.. 
	
	
	//입력받은 1010 채워넣는 for문 
	String str;
	for(int i=0; i<N; i++) {
		str=scan.next();
		for(int j=0; j<M; j++){
			mat[i][j]=Integer.parseInt(str.charAt(j)+"");
		}
	}
	//문제에서 인덱스가 1부터 시작하지만 인덱스로는 0,0 
	bfs(0,0);
	System.out.println(mat[N-1][M-1]); //마찬가지로 인덱스여서 -1로 처리 

}
public static void bfs(int x, int y) {
	//이동거리좌표 
	int[] dx= {-1, 0, 0, 1};
	int[] dy= {0, -1, 1, 0};
	int nx, ny;
	
	Queue<Integer> que= new LinkedList<Integer>();
	//큐에 x,y 넣어줌 
	que.offer(x); 
	que.offer(y);
	visited[x][y]=1; //방문한적있다고 1로 바꿈 

	
	while(!que.isEmpty()) {
		//x와 y를 가져와서 
		x=que.poll();
		y=que.poll();
		//상하좌우 이동핝 좌표계산 
		for(int j=0; j<4; j++) {
			nx= x+dx[j];
			ny= y+dy[j];
			//이동가능하다면 
			if(nx>=0&&nx<N&&ny>=0&&ny<M) {
				if(mat[nx][ny]>0&&visited[nx][ny]!=1) {
					visited[nx][ny]=1; //방문한적잇다고 바꾸고 
					//방문한 mat[][]들을 이전 mat[][]값으로 부터 누적 카운팅 해서 최종적으로는 mat[N-1][M-1]을 출력하도록 했습니다.???
					mat[nx][ny]= mat[x][y]+1;
					//이동을했으니, 그다음 좌표 nx, ny를 넣어줌 
					que.offer(nx);
					que.offer(ny);
				}
			}//if
		}
	}//while
	
}//bfs
}