그래프이론 - 섬의 개수(백준 4963번)

1. 그래프 이론 - 섬의 개수 (백준 4963번)

---

---

2. 그래프 이론을 이용한 문제 풀이

---

package _317324;
 
import java.util.Scanner;
 
public class Baekjoon4963NumberofIsland {
    static int count;
    static int[] dx= {-1,-1,0,1,1,1,0,-1};
    static int[] dy= {0,1,1,1,0,-1,-1,-1};
    static int[][] map=new int[50][50];
    static int height;
    static int weight;
    static void countIsland(int h,int w) {
        int nx=0;
        int ny=0;
        map[h][w]=2;
        for(int i=0;i<8;i++) {
            nx=w+dx[i];
            ny=h+dy[i];
            
            if(nx>=weight || nx<0 || ny>=height || ny<0) {
                continue;
            }
            if(map[ny][nx]==1) {
                countIsland(ny, nx);
            }
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        StringBuffer sb=new StringBuffer();
        while(true) {
            weight=sc.nextInt();
            height=sc.nextInt();
            if(weight==0 && height==0) break;
            
            for(int i=0;i<50;i++) {
                for(int j=0;j<50;j++) {
                    map[i][j]=0;
                }
            }
            for(int i=0;i<height;i++) {
                for(int j=0;j<weight;j++) {
                    map[i][j]=sc.nextInt();
                }
            }
            for(int i=0;i<height;i++) {
                for(int j=0;j<weight;j++) {
                    if(map[i][j]==1) {
                        countIsland(i, j);
                        count++;
                    }
                }
            }
            sb.append(count+"\n");
            count=0;
        }
        System.out.println(sb);
    }
 
}
 

문제의 풀이는 배열 안에 섬의 표시가 1로 표시가 되고 가로, 세로 및 대각선이 연결된 섬으로 인식이 되는 것이다. 1행부터 열을 탐색하여 1이 나오는 배열의 인덱스를 찾게 되면 그 배열의 좌표를 기준으로 countIsland 메소드를 호출하게 된다. 메소드 안에 좌표가 전달되면 전역 변수로 선언한 dx,dy 배열을 이용하여 연결된 섬을 찾게 된다. 좌표는 시작으로 부터 왼쪽, 왼쪽대각선위, 위, 오른쪽 대각선위, 오른쪽, 오른쪽 대각선 아래, 아래, 왼쪽대각선 아래를 뜻하게 된다. 그렇게 8방을 반복문으로 하나하나 따져봐서 인접한 1을 찾게 되는 것이다. 이 반복문 안에 첫번째 조건문이 뜻하는 바는 처음에 입력값으로 선언된 높이와 넓이의 직사각형을 벗어나는지를 따져보는 것이다. 만약 직사각형의 범위를 벗어나지 않으면서 팔방의 위치에 1이 존재한다면? 그 좌표를 방문했다는 표시로 모두 2로 배열의 값을 변경해준다.(그러면 더 이상 이섬은 탐색하지 않는다.)그리고 이섬은 연결된 섬으로 간주하고 그 섬의 좌표를 기준으로 countIsland 메소드를 다시 호출하게 된다. 즉, 그래프의 깊이우선 탐색을 실행하여 탐색하다가 더 이상 연결된 섬이 없을 때는 백트랙킹으로 이전의 좌표로 돌아가 이 좌표를 기준으로 다시 깊이 우선탐색을 실행하는 것이다. 그러다가 더 이상 탐색할 곳이 없게되면 함수를 종료하게 된다.(이 과정까지가 처음 발견된 1의 좌표를 기준으로 연결된 섬을 모두 탐색하고 난 후 종료하는 과정이다.)