[JAVA] 알고리즘 문제풀이 - DFS, BFS 기출문제 (섬나라 아일랜드)

DFS, BFS 기출문제 풀이

섬나라 아일랜드

• 설명 : N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.
  
  

만약 위와 같다면 섬의 개수는 5개입니다.

• 입력 : 첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다. 두 번째 줄부터 격자판 정보가 주어진다.
  
  

• 출력 : 첫 번째 줄에 섬의 개수를 출력한다.
  
  

• 풀이
  
  

import java.util.*;

public class Main {

    static int num;
    static int[][] map;
    static int[] row = {-1, 0, 1, 0, 1, 1, -1, -1};
    static int[] col = {0, -1, 0, 1, 1, -1, 1, -1};

    public void DFS(int a, int b){
        for(int i=0; i<8; i++){
            int r = a+row[i];
            int c = b+col[i];
            if(r>=0 && c>=0 && r<num && c<num && map[r][c]==1){
                map[r][c]=0;
                DFS(r, c);
            }
        }
    }
    public int solution(int r, int c) {
        int cnt = 0;

        for(int i=0; i<num; i++) {
            for (int j = 0; j < num; j++) {
                if (map[i][j] == 1) {
                    cnt++;
                    map[i][j] = 0;
                    DFS(i, j);
                }
            }
        }

        return cnt;
    }

    public static void main(String[] args) {
        Main t = new Main();

        Scanner scan = new Scanner(System.in);
        num = scan.nextInt();
        map = new int[num][num];
        for(int i=0; i<num; i++){
            for (int j=0; j<num; j++) {
                map[i][j] = scan.nextInt();
            }
        }

        System.out.println(t.solution(0, 0));
    }
}

• 정리
  
  • 움직여야하는 8방향을 미리 배열로 만들어둠
    
  • 메인 메서드에서 모든 좌표를 반복문을 통해서 돌되
    
  • 이때 값이 1인 지점이 나타나면 cnt를 증가시켜 섬 개수를 늘려줌
    
  • 그리고 미리 만들어둔 DFS 메소드안에서 현재 지점에서 8방향을 돌면서 1인 값이 나타나면 0으로 바꿔줌 (이미 섬으로 카운트된 영역을 중복체크 하지않기위해)
    
  • 모두 0으로 바뀌면 DFS메서드를 나와 다시 메인메서드를 돌면서 새로운 1값을 찾아 새로운 섬개수를 늘리는 방식