BFS너비우선 탐색

BFS

시작노드를 기준으로 가장 가까운 노드순으로 탐색을 하는 알고리즘이다.

구현법

우선 그래프의 생성은 DFS와 같다.
하지만 DFS에서는 재귀함수 또는 스택을 사용하여 구현 하였지만
BFS는 큐를 사용하여 구현한다.

적용대상

1. 주어진 그래프에서 찾을 목표노드가 여러개일 때 가장 가까운 노드순으로 방문하므로 최단거리의 목표노드를 찾는 문제에서 적용하기 좋다.

2. 미로찾기, 특정조건의 수 찾기같은 모든 경우의 수를 가지치기 하며 찾아가는 문제를 풀 때 적용하기 좋다.

BFS기본코드

public class Q26 {
	
	static ArrayList<Integer>[] arr;
	static boolean[] visit;
	static Queue<Integer> queue;
	
	public static void main(String[] args) throws Exception{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		
		int node = Integer.parseInt(st.nextToken()); //노드수
		int edge = Integer.parseInt(st.nextToken()); //엣지수
		int start = Integer.parseInt(st.nextToken()); //시작노드
		
		arr = new ArrayList[node+1];
		queue = new LinkedList<Integer>();
		visit = new boolean[node + 1];
		
		for(int i=1; i<=node; i++) {
			arr[i] = new ArrayList<Integer>();
		}
		
		for(int i=0; i<edge; i++) {
			st = new StringTokenizer(in.readLine());
			int a= Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			arr[a].add(b);
			arr[b].add(a);
		}
		
		BFS(start);
		for(int i=1; i<=node; i++) { //모든 노드를 방문 했는지 확인
			if(visit[i]==false) {
				BFS(i);
			}
		}
	}
	
	public static void BFS(int i) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(i);
		visit[i] = true;
		
		while(!queue.isEmpty()) {
			int n = queue.poll();
			System.out.print(n + " ");
			for(int j: arr[n]) {
				if(visit[j] == false) {
					queue.add(j);
					visit[j] = true; 
//j번노드와의 edge가 여러개 존재하면 j번노드가 poll()될 때까지 
j가 여러번 큐에 삽입될 수 있기 때문에 큐에 추가됨과 동시에 바로 방문배열에 저장을 해야한다.
				}
			}
		}
	}
}

미로찾기 문제 - 백준 2178

문제풀이 팁

1. 2차원에서 특정좌표를 기준으로 상하 좌우를 확인하기 위해
   {{-1,0}, {0,-1}, {1,0}, {0,1}} 와 같은 배열을 사용한다.

2. 특정문자를 기준으로 문자를 구분할 때는 split
   문자열의 자릿수를 기준으로 구분할 때는 substring

public class Q27 {

	static int[][] arr;
	static int n,m;
	static boolean[][] visit;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		visit = new boolean[n+1][m+1]; //좌표연산을 상상하기 쉽도록 1,1부터 구현	
		arr = new int[n+1][m+1];
		
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(in.readLine());
			String line = st.nextToken();
			for(int j = 1; j<=m; j++) {
				arr[i][j] = Integer.parseInt(line.substring(j-1,j)); // 문자열안에서 주어진 범위에 해당하는 문자를 추출하기 위해
																	 // substring 사용
			}
		}
		
		BFS(1,1);
		System.out.println(arr[n][m]);
	}
	
	public static void BFS(int a, int b) {
			Queue<int[]> queue = new LinkedList<int[]>(); // 큐안에 배열을 사용가능
			int[][] base = {{-1,0}, {0,-1}, {1,0}, {0,1}};// 현재 좌표의 상하좌우를 확인하기 위한 배열
			
			int[] point = {a,b};
			queue.add(point);
			visit[a][b] = true;
			
			while(!queue.isEmpty()) {
				
				point = queue.poll();

				for(int i=0; i<4; i++) {					
					int x = point[0] + base[i][0];  //상하좌우에 해당하는 좌표를 구성
					int y = point[1] + base[i][1];
					
					if(x>0 && y>0 && x<=n &&y<=m) { //좌표가 인덱스를 초과하지 않도록 조건입력
						if( visit[x][y] == false && arr[x][y] == 1) {
							queue.add(new int[] {x,y});
							visit[x][y] = true;
							arr[x][y] = arr[point[0]][point[1]] + 1; //깊이를 표시
						}
					}				
					 
					if(x== n&& y==m) { return; }					 
				}
			}
		}
		
	}

트리의 지름 구하기 - 백준 1167

코드생략

---

• 구현팁

  • 데이터 클래스 사용
    해당 문제에서는 노드번호와 엣지길이를 동시에 배열에 담아야 했다.
    이를 위해 노드번호와 엣지길이를 변수로 가지는 데이터 클래스를 구현하였고 이것을 배열에 담아 문제를 해결하였다.