深さ優先探索 | アルゴリズム[Java][AOJ 0118]


深さ優先探索(Depth-First Search、DFS、バックトラック法)の説明です。

😼 概要

深さ優先探索は次のように、子のないノードに行き着くまで順々に深く伸びていく探索です。



※ 数字は探索順

🚜 擬似コード

再帰を行う擬似コードです。

function 深さ優先探索(v)
v に訪問済みの印を付ける
v を処理する
for each v に接続している頂点 i do
if i が未訪問 then
深さ優先探索(i)

🚕 サンプル問題

🗻 Javaコード

深さ優先探索をJavaで解いた場合のコードです。

import java.util.Scanner;
public class Main {
static final char SEARCH_DONE = '.';
static final int[] dx = { -1, 0, 1, 0 };
static final int[] dy = { 0, 1, 0, -1 };
static int h, w;
static char[][] map;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
h = sc.nextInt();
w = sc.nextInt();
if (h == 0 && w == 0) {
break;
}
map = new char[h][];
for (int i = 0; i < h; i++) {
map[i] = sc.next().toCharArray();
}
int count = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
char current = map[i][j];
if (current != SEARCH_DONE) {
depthFirstSearch(i, j, current);
count++;
}
}
}
System.out.println(count);
}
}
private static void depthFirstSearch(int y, int x, char target) {
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= w || ny < 0 || ny >= h) {
continue;
}
if (map[ny][nx] == target) {
map[ny][nx] = SEARCH_DONE;
depthFirstSearch(ny, nx, target);
}
}
}
}

🐹 参考リンク

🖥 VULTRおすすめ

VULTR」はVPSサーバのサービスです。日本にリージョンがあり、最安は512MBで2.5ドル/月($0.004/時間)で借りることができます。4GBメモリでも月20ドルです。 最近はVULTRのヘビーユーザーになので、「ここ」から会員登録してもらえるとサービス開発が捗ります!

📚 おすすめの書籍