[DFS] Flood Fill

가능한 영역에 3으로 색칠하기

 

 

 

 

 

 

 

import java.util.*;

public class Main {	
	
	// 이동방향
	static int[][] D = {
			{0,1},
			{0,-1},
			{1,0},
			{-1,0}
	};
	
	// MAP
	static int[][] matrix = {
		{0,0,0,0,0},
		{0,0,0,1,1},
		{0,0,0,1,0},
		{1,1,1,1,0},
		{0,0,0,0,0}
	};

	public static void main(String[] args) {				
		
		Scanner sc = new Scanner(System.in);
		// 출발지
		int sRow = sc.nextInt();
		int sCol = sc.nextInt();
		
		// 색칠할 숫자
		int c = sc.nextInt();
		
		dfs(sRow, sCol, c);
		
		// 출력
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix.length; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	public static void dfs(int sRow, int sCol, int c) {
		int m = matrix.length;
		int n = matrix[0].length;
		boolean[][] visit = new boolean[m][n];	// 방문 기록
		Stack<Node> stack = new Stack<Node>();	// DFS는 stack사용
		
		stack.add(new Node(sRow, sCol));		
		
		while(!stack.isEmpty()) {
			Node node = stack.pop();	// 꺼내서 확인
			int row = node.row;
			int col = node.col;			
			visit[row][col] = true;	// 방문 표시
			
            matrix[row][col] = c;	// 실제 작업 : 색칠하기
			
			for (int i = 0; i < 4; i++) {
				int nRow = row + D[i][0];
				int nCol = col + D[i][1];
				if(nRow < 0 || nRow >= m || nCol < 0 || nCol >= n)
					continue;
				if(visit[nRow][nCol])
					continue;
				if(matrix[nRow][nCol] == 1)
					continue;
				stack.push(new Node(nRow, nCol));
			}
			
		}
		
    }
	
	// Node 클래스
	static class Node {
		int row;
		int col;
		
		public Node(int row, int col) {
			this.row = row;
			this.col = col;		
		}
		
	}
		
}

 

 

결과

 

DFS 참고 = >https://youtu.be/0Njv04WiLV0