암시적 그래프 dfs 템플릿

int[][] grid = {
    {1, 1, 1, 1},
    {0, 1, 0, 1},
    {0, 1, 0, 1},
    {1, 0, 1, 1}
};

public class ImplicitGraphDFS {
		static boolean[][] visited;
		static int[][] grid;
		static int[] dr = {1, -1, 0, 0};
		static int[] dc = {0, 0, 1, -1};
		static int rowLength;
		static int colLength;
		
		public static boolean isValid(int r, int c) {
		    return 0 <= r && r < rowLength && 0 <= c && c < colLength;
		}
		
		public static void main(String[] args) {
		    grid = new int[][] {
				    {1, 1, 1, 1},
				    {0, 1, 0, 1},
				    {0, 1, 0, 1},
				    {1, 0, 1, 1}
				};
		    rowLength = grid.length;
		    colLength = grid[0].length;
		    visited = new boolean[rowLength][colLength];
		    dfs(0, 0);
		}
		
		public static void dfs(int r, int c) {
		    // 현재 노드 방문
		    visited[r][c] = true;
		    
		    // 다음 노드 방문
		    for (int i = 0; i < 4; i++) {
		        int nextRow = r + dr[i];
		        int nextCol = c + dc[i];
		        if (isValid(nextRow, nextCol)) {
		            if (!visited[nextRow][nextCol]) {
		                dfs(nextRow, nextCol);
		            }
		        }
		    }
		}
}