৫টি সহজ BFS/DFS কোডিং প্রবলেম ও সমাধান (Java)

আগের ফাইলে ছিল Tree — এবার BFS/DFS-এর আসল খেলার মাঠ: Grid ও Graph। ইন্টারভিউতে graph traversal প্রবলেমের প্রায় সবই এই ৫টি প্যাটার্নের রূপভেদ।

প্রবলেম ১: Number of Islands (LeetCode 200) — Grid DFS

প্রশ্ন: একটি 2D grid-এ '1' = ভূমি, '0' = পানি। কতগুলো দ্বীপ (island) আছে বের করুন। পাশাপাশি (উপর-নিচ-ডান-বাম) যুক্ত ভূমিগুলো একটি দ্বীপ।

চিন্তার ধাপ: পুরো grid ঘুরুন। যখনই একটি '1' পাবেন — এটি একটি নতুন দ্বীপ, counter বাড়ান, আর DFS দিয়ে ওই দ্বীপের সব ভূমি "ডুবিয়ে দিন" ('0' করে দিন), যাতে একই দ্বীপ দ্বিতীয়বার গোনা না হয়। Grid নিজেই visited-এর কাজ করছে — আলাদা visited array লাগছে না।

সমাধান:

public int numIslands(char[][] grid) {
    int count = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == '1') {
                count++;
                sink(grid, r, c);  // পুরো দ্বীপটি ডুবিয়ে দিন
            }
        }
    }
    return count;
}

private void sink(char[][] grid, int r, int c) {
    // সীমার বাইরে বা পানি হলে থামুন
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
            || grid[r][c] == '0') {
        return;
    }
    grid[r][c] = '0';  // visited হিসেবে চিহ্নিত

    sink(grid, r + 1, c);  // নিচ
    sink(grid, r - 1, c);  // উপর
    sink(grid, r, c + 1);  // ডান
    sink(grid, r, c - 1);  // বাম
}

Complexity: Time O(m×n) — প্রতিটি cell সর্বোচ্চ একবার sink হয়। Space O(m×n) worst case (recursion stack, পুরো grid একটাই দ্বীপ হলে)।

ইন্টারভিউ টিপ: "Input mutate করা কি ঠিক?" — জিজ্ঞেস করুন। আপত্তি থাকলে আলাদা boolean[][] visited ব্যবহার করুন। এই একটি প্রশ্ন করাই senior signal।

প্রবলেম ২: Flood Fill (LeetCode 733) — Grid DFS

প্রশ্ন: Paint bucket tool-এর মতো — একটি pixel (sr, sc) থেকে শুরু করে তার সাথে যুক্ত একই রঙের সব pixel-কে নতুন রঙে রাঙান।

চিন্তার ধাপ: Number of Islands-এর ছোট ভাই। শুরুর pixel-এর রঙ মনে রাখুন, তারপর DFS — যেখানেই ওই পুরনো রঙ পাবেন, নতুন রঙ বসান।

সমাধান:

public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
    int oldColor = image[sr][sc];
    if (oldColor != newColor) {  // এই চেকটি না দিলে infinite loop!
        fill(image, sr, sc, oldColor, newColor);
    }
    return image;
}

private void fill(int[][] image, int r, int c, int oldColor, int newColor) {
    if (r < 0 || r >= image.length || c < 0 || c >= image[0].length
            || image[r][c] != oldColor) {
        return;
    }
    image[r][c] = newColor;

    fill(image, r + 1, c, oldColor, newColor);
    fill(image, r - 1, c, oldColor, newColor);
    fill(image, r, c + 1, oldColor, newColor);
    fill(image, r, c - 1, oldColor, newColor);
}

Complexity: Time O(m×n), Space O(m×n) recursion stack।

ইন্টারভিউ টিপ: oldColor == newColor হলে কিছু না করেই return — এই edge case মিস করলে infinite recursion → StackOverflowError। Interviewer-রা এই case টি ইচ্ছা করে test-এ রাখেন।

প্রবলেম ৩: Rotting Oranges (LeetCode 994) — Multi-source BFS

প্রশ্ন: Grid-এ 2 = পচা কমলা, 1 = তাজা কমলা, 0 = খালি। প্রতি মিনিটে পচা কমলার পাশের তাজা কমলাগুলো পচে যায়। সব কমলা পচতে কত মিনিট লাগবে? সম্ভব না হলে -1।

চিন্তার ধাপ: "সবচেয়ে কম সময়/ধাপ" শুনলেই BFS। বিশেষত্ব: একাধিক উৎস — সব পচা কমলা একসাথে queue-তে দিয়ে শুরু করুন (multi-source BFS)। প্রতিটি BFS level = ১ মিনিট। Tree-র level order traversal-এর সেই levelSize snapshot প্যাটার্নটিই এখানে কাজে লাগে।

সমাধান:

public int orangesRotting(int[][] grid) {
    Queue<int[]> queue = new LinkedList<>();
    int fresh = 0;

    // সব পচা কমলা queue-তে, তাজা কমলা গণনা
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 2) queue.offer(new int[]{r, c});
            else if (grid[r][c] == 1) fresh++;
        }
    }
    if (fresh == 0) return 0;  // পচানোর কিছুই নেই

    int minutes = 0;
    int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    while (!queue.isEmpty() && fresh > 0) {
        int levelSize = queue.size();  // এই মিনিটে যারা পচাবে
        for (int i = 0; i < levelSize; i++) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length
                        && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;   // পচে গেল = visited
                    fresh--;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}

Complexity: Time O(m×n), Space O(m×n)।

ইন্টারভিউ টিপ: dirs array দিয়ে চার দিক লেখা — চারটি আলাদা if-এর বদলে — কোড ছোট ও ভুলমুক্ত রাখে। আর "কেন DFS নয়?" — কারণ DFS shortest path/minimum time দেয় না, BFS level-by-level ছড়ায় বলেই প্রতি level = ১ মিনিট কাজ করে।

প্রবলেম ৪: Cycle Detection in Undirected Graph — DFS

প্রশ্ন: n টি node (0 থেকে n-1) ও edge list দেওয়া আছে। Graph-এ cycle আছে কিনা বের করুন। (এটিই LeetCode 261 "Graph Valid Tree"-এর মূল অংশ।)

চিন্তার ধাপ: Undirected graph-এ DFS চালান। যদি এমন কোনো visited node-এ পৌঁছান যেটি আপনার সরাসরি parent নয় — cycle পাওয়া গেছে। Parent-কে বাদ দিতে হবে, কারণ undirected edge-এ A→B গেলে B থেকে A তো দেখা যাবেই — সেটা cycle নয়।

সমাধান:

public boolean hasCycle(int n, int[][] edges) {
    // Adjacency list তৈরি
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);  // undirected: দুই দিকেই
    }

    boolean[] visited = new boolean[n];
    for (int i = 0; i < n; i++) {           // disconnected graph-ও সামলানো
        if (!visited[i]) {
            if (dfs(adj, visited, i, -1)) return true;
        }
    }
    return false;
}

private boolean dfs(List<List<Integer>> adj, boolean[] visited,
                    int node, int parent) {
    visited[node] = true;
    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            if (dfs(adj, visited, neighbor, node)) return true;
        } else if (neighbor != parent) {
            return true;  // visited কিন্তু parent নয় → cycle!
        }
    }
    return false;
}

Complexity: Time O(V + E), Space O(V + E)।

ইন্টারভিউ টিপ: Follow-up প্রায় নিশ্চিত — "directed graph হলে?" উত্তর: parent trick কাজ করবে না; তিন রঙ (white/gray/black) বা recursion stack tracking লাগবে — gray (বর্তমান path-এ থাকা) node-এ ফিরলেই cycle। আরেকটি বিকল্প: Union-Find — বলতে পারলেই bonus point।

প্রবলেম ৫: Shortest Path in Binary Matrix (LeetCode 1091) — BFS

প্রশ্ন: n×n grid-এ 0 = চলা যায়, 1 = ব্লক। উপরের-বাম কোণ থেকে নিচের-ডান কোণ পর্যন্ত সবচেয়ে ছোট path-এর দৈর্ঘ্য কত (৮ দিকেই চলা যায়)? পথ না থাকলে -1।

চিন্তার ধাপ: Unweighted grid/graph-এ shortest path মানেই BFS — DFS এখানে ভুল উত্তর দেবে। এখানে ৮ দিক (কোণাকুণিসহ)। Path length queue-র ভেতরে বহন করুন অথবা level গুনুন।

সমাধান:

public int shortestPathBinaryMatrix(int[][] grid) {
    int n = grid.length;
    if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;

    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{0, 0, 1});  // {row, col, pathLength}
    grid[0][0] = 1;  // visited চিহ্নিত (queue-তে ঢোকানোর সময়েই!)

    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        int r = cell[0], c = cell[1], dist = cell[2];

        if (r == n - 1 && c == n - 1) return dist;  // গন্তব্যে পৌঁছে গেছি

        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                grid[nr][nc] = 1;  // ঢোকানোর সময়েই visited
                queue.offer(new int[]{nr, nc, dist + 1});
            }
        }
    }
    return -1;
}

Complexity: Time O(n²), Space O(n²)।

ইন্টারভিউ টিপ: সবচেয়ে সূক্ষ্ম ভুল — visited চিহ্নিত করা queue থেকে বের করার সময়, ঢোকানোর সময় নয়। তাতে একই cell বহুবার queue-তে ঢুকে TLE হয়। Enqueue করার মুহূর্তেই mark করুন। Follow-up: "প্রতিটি ঘরে ভিন্ন cost থাকলে?" → তখন BFS নয়, Dijkstra (PriorityQueue) — এই এক লাইনের উত্তর জানা থাকলেই যথেষ্ট।

BFS vs DFS — কোনটি কখন?

মূল প্যাটার্ন — মনে রাখুন

১. Grid = graph: প্রতিটি cell একটি node, পাশের cell গুলো neighbor। dirs array দিয়ে দিক সামলান। ২. Visited অপরিহার্য — grid mutate করে অথবা আলাদা array-তে। BFS-এ mark করুন enqueue-এর সময়েই। ৩. "Minimum" শব্দ দেখলেই BFS, "সব ঘুরে দেখা/গোনা" হলে DFS। ৪. Boundary check প্রথমে — r < 0 || r >= rows || ... — এই লাইনটি প্রতিটি সমাধানে এক ছাঁচে লেখা অভ্যাস করুন।

পরবর্তী ধাপ: এগুলো আয়ত্তে এলে medium-এ যান — Course Schedule (207, topological sort), Clone Graph (133), Word Ladder (127), Pacific Atlantic Water Flow (417)।