package basic.bfs;

import basic.algorithm.AbstractGraphAlgorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class GraphBFS extends AbstractGraphAlgorithm {

    private static final int[] dx = {-1, 1, 0, 0}; // 상하좌우
    private static final int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        GraphBFS bfs = new GraphBFS();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        bfs.init(br);
        bfs.input(br);
        bfs.printAsGraph();

        System.out.println("BFS 탐색 시작 (시작점 입력): ");
        System.out.print("행(row): ");
        int startRow = Integer.parseInt(br.readLine());
        System.out.print("열(col): ");
        int startCol = Integer.parseInt(br.readLine());

        bfs.bfs(startRow, startCol);
    }

    private void bfs(int x, int y) {
        Queue<Node> queue = new LinkedList<>();

        // 시작점이 이동 불가능한 경우
        if (field[x][y] != 1) {
            System.out.println("시작 지점이 이동 불가능합니다.");
            return;
        }

        visited[x][y] = true;
        printAsVisited();
        queue.add(new Node(x, y));

        while (!queue.isEmpty()) {
            Node now = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                if (nx >= 0 && nx < field.length &&
                    ny >= 0 && ny < field[0].length &&
                    !visited[nx][ny] && field[nx][ny] == 1) {

                    visited[nx][ny] = true;
                    printAsVisited();
                    queue.add(new Node(nx, ny));
                }
            }
        }
    }

    private static class Node {
        int x;
        int y;

        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}