자바(Java) 알고리즘 문제 풀이 - 섬나라 아일랜드(DFS)

문제 이해

- 섬의 개수를 구하라

 

해결 전략

- 2차원 board 배열을 순회하면서 board[x][y] = 1을 발견하면,

  DFS 순회를 시작합니다.

- 한 번 방문한 점들은 board[x][y] = -1로 변경해서, 재방문하지 않도록 합니다. 

 

구현

import java.util.*;

public class Main {
	static int answer=0, n;
	static int[] dx={-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dy={0, 1, 1, 1, 0, -1, -1, -1};
	public void DFS(int x, int y, int[][] board){
		
		 
		  for(int i=0; i<8; i++){
		      int nx = x+dx[i];
		      int ny = y+dy[i];
		      
		      if(0<= nx && nx<n && 0<=ny && ny<n && board[nx][ny] == 1){
		          board[nx][ny] = -1;
		          DFS(nx, ny, board);
		      }
		  }
		
	}
	public void solution(int[][] board){
		
		for(int i=0; i<n; i++)
		  for(int j=0; j<n; j++){
		      if(board[i][j] == 1){
	              board[i][j] = -1;     
		          DFS(i, j, board);
		          answer++;
		      }
		  }
		
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		int[][] arr=new int[n][n];
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				arr[i][j]=kb.nextInt();
			}
		}
		T.solution(arr);
		System.out.println(answer);
	}
}

 

피드백

- 없음