BFS(너비 우선 탐색)

너비우선탐색 개념 

 

탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후, 방문했던 정점을 시작점으로 하여 그 시작점과 인접한 정점을 다시 차례로 방문하는 방식을 말한다. 이 때 방문했던 인접 정점도 순서대로 다시 인접 정점을 탐색해야 하므로 선입선출 형태의 자료구조인 Queue(큐)를 활용한다. 방문 여부 검사를 통해 무한루프에 빠지지 말아야 한다. 

 

너비우선탐색 특징 

 

1) 시작 노드로부터 단계적으로 거리에 따라 탐색한다.

2) 재귀적으로 작동하지 않는다.

3) 프림 및 다익스트라 알고리즘과 유사하다.

 

 

구현 방식1) 인접행렬

두 정점이 연결되어 있는 여부를 한 눈에 확인 가능하나, 시간도 많이 사용하고 메모리 낭비가 심하다. 들어오고 나가는 간선이 한 눈에 보이기 때문에 간선이 많을 때(밀집 그래프) 그리고 단방향일 때만 사용

 

구현 방식2) 인접리스트

가장 많이 사용하는 표현 방법으로서 공간적 및 시간적으로 유리함 Arraylist나 linkedlist를 활용해 구현하며 정점들을 노드 형태로 연결한다. 인접 행렬에 비해 메모리 낭비가 적지만, 특정 정점들이 직접 연결되어 있는 여부를 확인하기 위해서는 기준 정점의 노드를 모두 조회해봐야 한다.

 

 

너비 우선 탐색의 활용

 

최단 길이를 구하는 문제의 경우, 인접한 노드부터 차례로 방문하기 때문에 시작과 끝 정점을 안다면 BFS를 사용하는 것이 적합

 

백준 7576

특정 지점을 기준으로 4방의 토마토가 영향을 주는 방식이므로 BFS를 사용하는 것이 좋을 것 같다.

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

public class Main {
	static int n, m;
	static int[][] arr;
	static Queue<box> qu;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		m = sc.nextInt();
		n = sc.nextInt();

		arr = new int[n][m];

		boolean flag = true;
		for (int r = 0; r < n; r++) {
			for (int c = 0; c < m; c++) {
				arr[r][c] = sc.nextInt();
				if (arr[r][c] != 1 && arr[r][c] != -1) {
					flag = false;
				}
			}
		}

		if (flag) { // 처음부터 다 익어있었어요
			System.out.println(0);
			sc.close();
			return;
		}
		qu = new LinkedList<>();
		for (int r = 0; r < n; r++) {
			for (int c = 0; c < m; c++) {
				if (arr[r][c] == 1) {
					box b = new box(r, c);
					qu.add(b);
				}
			}
		}
		System.out.println(Tomato());
		sc.close();
	}

	private static int Tomato() {
		int max = Integer.MIN_VALUE;
		int[][] drc = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

		while (!qu.isEmpty()) {
			box curr = qu.poll();

			for (int d = 0; d < drc.length; d++) {
				int nr = curr.row + drc[d][0];
				int nc = curr.column + drc[d][1];

				if (nr >= 0 && nr < n && nc >= 0 && nc < m) { // 경계를 넘지 않을 때
					if (arr[nr][nc] == 0) {
						arr[nr][nc] = arr[curr.row][curr.column] + 1;
						box b = new box(nr, nc);
						qu.add(b);
					}
				}
			}
		}
		for (int r = 0; r < n; r++) { // 안 익은 토마토가 있어요
			for (int c = 0; c < m; c++) {
				if (arr[r][c] == 0) {
					return -1;
				}
				max = Math.max(max, arr[r][c]);
			}
		}
		return max - 1;
	}

	public static class box {
		int row;
		int column;

		public box(int row, int column) {
			this.row = row;
			this.column = column;
		}
	}
}