Java向け競プロライブラリ(幅優先探索)

幅優先探索を使用する問題向けのライブラリです。例えば以下のような問題に対して使用すると有用です。

AtCoder Beginner Contest 007 C - 幅優先探索

AtCoder Beginner Contest 204 C - Tour

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

final class BfsExecutor {

	private static final char UNREACHABLE_GRID = '#';
	private static final int INF = 1 << 30;

	/**
	 * 幅優先探索により、スタート位置からの最短距離を記録した二次元配列を取得する
	 * @param grid 横幅と高さが定まった二次元グリッド
	 * @param sx スタート位置のx座標
	 * @param sy スタート位置のy座標
	 * @return スタート位置からの最短距離を記録した二次元配列
	 */
	public static int[][] getGridDistanceMemory(char[][] grid, int sx, int sy) {
		int h = grid.length;
		int w = grid[0].length;
		int[][] distances = new int[h][w];
		for (int[] row : distances) {
			Arrays.fill(row, INF);
		}

		Deque<Integer> qx = new ArrayDeque<Integer>();
		Deque<Integer> qy = new ArrayDeque<Integer>();
		int[] dx = { 1, 0, -1, 0 };
		int[] dy = { 0, 1, 0, -1 };

		distances[sy][sx] = 0;
		qx.addLast(sx);
		qy.addLast(sy);

		while (!qx.isEmpty()) {
			int px = qx.pollFirst();
			int py = qy.pollFirst();

			for (int i = 0; i < 4; ++i) {
				int nx = px + dx[i];
				int ny = py + dy[i];

				// 範囲外ならば無視
				if (!(0 <= nx && nx <= w - 1) || !(0 <= ny && ny <= h - 1)) {
					continue;
				}

				// 行けないマスならば無視
				if (grid[ny][nx] == UNREACHABLE_GRID) {
					continue;
				}

				// 訪問済みのマスならば無視
				if (distances[ny][nx] < INF) {
					continue;
				}

				distances[ny][nx] = distances[py][px] + 1;
				qx.addLast(nx);
				qy.addLast(ny);
			}
		}

		return distances;
	}

	/**
	 * 幅優先探索を行い、頂点に隣接するノードを記録したリストを返す
	 * @param adjNodesToEach 各ノードに隣接しているノードを記録した2次元リスト
	 * @param top 頂点
	 * @param visited 訪問済みの頂点か否か判定用配列(要素数はノードの数に等しい)
	 * @return 頂点に隣接しているノード番号のリスト
	 */
	public static List<Integer> getAdjacentNodesToTop(ArrayList<Integer>[] adjNodesToEach, int top, boolean[] visited) {
		List<Integer> res = new ArrayList<Integer>();

		Deque<Integer> q = new ArrayDeque<Integer>();
		res.add(top);
		visited[top] = true;
		q.addLast(top);

		while (!q.isEmpty()) {
			int prevNode = q.pollFirst();

			for (int i = 0, f = adjNodesToEach[prevNode].size(); i < f; ++i) {
				int adjNode = adjNodesToEach[prevNode].get(i);

				if (visited[adjNode]) {
					continue;
				}

				res.add(adjNode);
				visited[adjNode] = true;
				q.addLast(adjNode);
			}
		}

		return res;
	}

}

 

幅優先探索は以下のような疑似コードで一般的に表現できます

function bfs(top) {
	// 空のキューQを定義
	// topに訪問済みの印をつける
	// topをQに追加

	while (Qが空でない) {
		// prevNode ← Qの先頭から取り出す

		for each (prevNodeに接続しているノードadj) {
			if (adjが訪問済み) {
				continue;
			}

			// adjに訪問済みの印をつける
			// adjをQに追加
			// adjに所望の処理を行う
		}
	}
}