東大ニート

東大卒のニートが勉強したことをメモするブログ

<アルゴリズム>深さ優先探索

AOJの0118の問題(Property Distribution | Aizu Online Judge)を深さ優先探索で解いてみました。今日は深さ優先探索について、勉強した内容をメモします。

 

深さ優先探索とは

深さ優先探索 - Wikipediaによると、「深さ優先探索(ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう)は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。」とのことです。

以下のように、子のないノードに行き着くまで順々に深く伸びていくイメージです(ノードの番号が探索される順番です)。

f:id:todai_neet:20150914155755j:plain

使いどころ

現時点での理解なので、少し自信ないですが

  • 全パターン調べたい
  • 漸化式で表現できそう

という時は深さ優先探索が使えないか考えてみるといい気がします。 

アルゴリズムのポイント

使い方のイメージとして、AOJ0118で私がJavaで書いたコードは以下のようになります。

  1. import java.util.Scanner;
  2. import java.util.Deque;
  3. import java.util.ArrayDeque;

  4. public class Main {

  5.    static Scanner sc = new Scanner(System.in);

  6.    static int h, w;

  7.    static char fruitFarm;

  8.    static int dx = {-1, 0, 1, 0};

  9.    static int dy = {0, -1, 0, 1};

  10.    static Deque<int> stack

  11.    public static void main(String args){ 

  12.       while (true) {

  13.          h = sc.nextInt();

  14.          w = sc.nextInt();

  15.          if (h == 0 && w == 0) break;

  16.          //fruitFarm配列の作成

  17.          fruitFarm = new char[h][w];

  18.          for (int i = 0; i < h; i++) {

  19.             String s = sc.next();

  20.             for (int j = 0; j < w; j++) {

  21.                fruitFarm[i][j] = s.charAt(j);

  22.             }

  23.          }

  24.          int answer = 0;

  25.          for (int i = 0; i < h; i++) {

  26.             for (int j = 0; j < w; j++) {

  27.                if (fruitFarm[i][j] != '.') {

  28.                   stack = new ArrayDeque<int>();

  29.                   stack.offerLast(new int{i, j});

  30.                   //stackが空になった=それまで調べていた同じ種類の果物の区画が調べ終わった

  31.                   while (!stack.isEmpty()) {

  32.                      int xy = stack.pollLast();

  33.                      int x = xy[0];

  34.                      int y = xy[1];

  35.                      dfs(x, y);

  36.                   }

  37.                   answer++;

  38.                }

  39.             }

  40.          }

  41.          System.out.println(answer);

  42.       }

  43.    }

  44.  

  45.    static void dfs(int x, int y) {

  46.       char target = fruitFarm[x][y];

  47.       fruitFarm[x][y] = '.';

  48.       //移動する4方向をループ

  49.       for (int k = 0; k < 4; k++) {

  50.          int nx = x + dx[k];

  51.          int ny = y + dy[k];

  52.          //nxnyが区画の範囲内かどうか、同じ種類の果物が植えられているか判定

  53.          if (target != '.' && nx >= 0 && nx <= h - 1 && ny >= 0 && ny <= w - 1 && fruitFarm[nx][ny] == target) {

  54.             stack.offerLast(new int{nx, ny});
  55.          }
  56.       }

  57.    }

  58. }

特にポイントとなるのは

  • 33行目〜38行目のスタックを作成して、最初の位置情報を渡すところ
  • 47行目〜59行目の探索を行い、該当のものがあればスタックに情報を追加するところ

です。