[BFS] Java 정리

김태민·2022년 4월 8일
0

알고리즘

목록 보기
35/77

1. 개념

BFS 너비 우선 탐색(Breadth First Search)
"꼼꼼하게 좌우를 살피며 다니자"와 같이 시작 정점으로부터 가까운 정점을 먼저 방문하고

멀리 떨어져 있는 정점을 나중에 방문하는 알고리즘이다.

시작 정점을 지나고 나면 깊이가 1인 모든 정점을 방문하고, 그다음에는 깊이가 2인 모든 정점을 방문한다.

이런 식으로 한 단계씩 깊이를 더해가며 해당 깊이에 있는 모든 정점들을 방문해 나가다가 나중에는 더 이상 방문할 곳이 없을 때 탐색을 종료한다.

  • 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

  • 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

BFS의 특징
BFS는 시작 정점으로부터 거리가 가까운 정점의 순서로 탐색한다. (거리 1부터 2, 3 순서대로)
그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.)
BFS는 재귀적으로 동작하지 않는다.
BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
즉, 선입선출(FIFO) 원칙으로 탐색
일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.

출처: https://minhamina.tistory.com/36

2. 코드

package mymain;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class BOJ_2178 {

	// 전역 변수 설정
	static int[][] map; // 미로 탐색할 배열 생성
	static int n; // 미로 배열 크기
	static int m;
	static boolean[][] visited; // 방문 체크할 배열 생성
	static int[] dx = { 0, 0, -1, 1 }; // 상하좌우로 움직일 배열 생성
	static int[] dy = { -1, 1, 0, 0 };

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력 받을 버퍼리더 생성
		StringTokenizer st = new StringTokenizer(br.readLine());    			  // 한 줄을 읽어와서 split함. 
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		
		// 입력
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++) {
				map[i][j] = s.charAt(j) - '0'; // ex) j = 1이라면 아스키 코드 값으로 49이다. 여기서 '0'(아스키코드값 48)을 뺴면 숫자 1이 나온다.
			}
		}

		visited = new boolean[n][m]; // 방문 배열 초기화
		visited[0][0] = true; // 시작점(문제에선 (1, 1)) 방문 처리
		BFS(0, 0);
		System.out.println(map[n - 1][m - 1]);

	}

	public static void BFS(int x, int y) {
		// TODO Auto-generated method stub
		
		Queue<int[]> q = new LinkedList<>(); // bfs를 진행할 큐 생성
		q.add(new int [] {x, y});			 // 큐에 시작 좌표 추가
		
		while (!q.isEmpty()) {				 // 조건: 큐가 비어있지 않을 때,
			
			int now [] = q.poll(); 			 // 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고, 해당 요소를 큐에서 제거함.
			
			for (int i = 0; i < 4; i++) {	 // 상 하 좌 우로 탐색
				
				int nextX = now[0] + dx[i];  // 다음 좌표는 현재 좌표에서 dx와 dy를 순회하면서 움직임
				int nextY = now[1] + dy[i];
				
				if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m) { // 미로를 벗어난다면, 스킵
					continue;
				}
				if (visited[nextX][nextY] == true || map[nextX][nextY] == 0) { // 방문했거나, 벽을 만난다면, 스킵
					continue;
				}
				
				q.add(new int [] {nextX, nextY});					// 그 외의 경우 큐에 인큐(푸쉬)하고 
				map[nextX][nextY] = map[now[0]][now[1]] +1;			// 다음 좌표에 현재 거리에서 +1만큼 추가
				visited[nextX][nextY] = true;						// 방문 체크
				
			}
		}
	}

}

3. 정리

맨 처음 프로그래밍 언어 입문이 C#이라 그런지 python보다 훨씬 직관적이고 잘 이해가 됐다.
DFS와 BFS가 나오면 항상 쩔쩔맸는데, 이번에 확실히 정리해서 어떤 문제든 풀 수 있게 해야겠다.
최단거리와 인접 노드 탐색 두 가지 유형을 중심으로 다양한 문제를 풀어보면서 정리할 예정이다.

profile
어제보다 성장하는 개발자

0개의 댓글