ヤマカサのプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

深さ優先探索

AtCoder Typical Contest 001 A - 深さ優先探索

atc001.contest.atcoder.jp

AtCoderの問題のなかで深さ優先探索に関する問題を解きました。深さ優先探索 (Depth First Search) は、グラフの探索アルゴリズムです。

この問題は迷路のスタートからゴールまでの道があるかどうかという問題です。

迷路を解くアルゴリズム幅優先探索を使ったことがありますが、深さと幅の違いは、スタックを使うかキューを使うかの違いです。

参考として、次のサイトを載せます。 qiita.com

コード

import java.awt.Point;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class ProblemA2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int H = scan.nextInt();
        int W = scan.nextInt();

        String [][]c = new String[H][W];
        String []s = new String[H];
        for(int i = 0; i < H; i++) {
            s[i] = scan.next();
        }
        int sx = 0;
        int sy = 0;
        int gx = 0;
        int gy = 0;
        for(int i = 0; i < H; i++) {
            for(int j = 0; j < W; j++) {
                c[i][j] = s[i].substring(j, j + 1);
                if(c[i][j].equals("s")) {
                    sx = j;
                    sy = i;
                }
                if(c[i][j].equals("g")) {
                    gx = j;
                    gy = i;
                }
            }
        }
        scan.close();


        int state[][] = new int[H][W];

        for(int i = 0; i < H; i++) {
            for(int j = 0; j < W; j++) {
                if(c[i][j].equals("#")) {
                    state[i][j] = 2;
                }else {
                    state[i][j] = 0;
                }
            }
        }


        Point start = new Point(sx, sy);
        Deque<Point> stack = new ArrayDeque<Point>();
        stack.push(start);
        int []dx = {1, -1, 0, 0};
        int []dy = {0, 0, 1, -1};

        while(!stack.isEmpty()) {
            Point temp = stack.pop();
            int tempX = (int)temp.getX();
            int tempY = (int)temp.getY();
            state[tempY][tempX] = 1;
            for(int i = 0; i < 4; i++) {
                int nextX = tempX + dx[i];
                int nextY = tempY + dy[i];
                if(nextX >=0 && nextY >= 0 && nextX < W && nextY < H) {
                    if(nextX == gx && nextY == gy) {
                        System.out.println("Yes");

                        System.exit(0);
                    }
                    if(state[nextY][nextX] == 0) {
                        state[nextY][nextX] = 1;
                        stack.push(new Point(nextX, nextY));
                        //System.out.println(nextX + " : " + nextY);
                    }

                }
            }

        }

        System.out.println("No");

    }
}