[Algorithm] DFS

package Algorithm;

import java.util.*;

public class dfs {

    static class Pair{
        int x, y;
        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) {

        int[][] board = new int[502][502];  // 1이 파란 칸, 0이 빨간 칸에 대응
        int[][] visited = new int[502][502];    // 해당 칸을 방문했는지 여부를 저장
        int N = 7;  // 행의 수
        int M = 10;     // 열의 수
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        Stack<Pair> stack = new Stack<>();
        visited[0][0] = 1;  // (0, 0)을 방문했다고 명시
        stack.push(new Pair(0,0));  // 스택에 시작점인 (0, 0)을 삽입

        while(!stack.isEmpty()){
            Pair cur = stack.pop();
            for(int d=0; d<4; d++){ // 상하좌우 칸
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];
                if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;    // 범위 밖일 경우 넘어감
                if(visited[nx][ny] == 1 || board[nx][ny] != 1) continue;    // 이미 방문한 칸이거나 파란 칸이 아닐 경우
                visited[nx][ny] = 1;    // (nx, ny)를 방문했다고 명시
                stack.push(new Pair(nx, ny));
            }
        }
    }
}

 

💬 참고

https://blog.encrypted.gg/942