[백준 4963] 섬의 개수

출처 : https://www.acmicpc.net/problem/4963

---

BFS문제입니다 

전체 소스 입니다

public class Q4963 {
	public static int[] nX = {-1, 0, 1, -1, 1, -1, 0, 1};
	public static int[] nY = {-1, -1, -1, 0, 0, 1, 1, 1};
	
	public static void main(String[] args) throws IOException{
		Q4963 to = new Q4963();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int w;
		int h;
		int[][] arr;
		while(true) {
			st = new StringTokenizer(br.readLine());
			
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			
			if(w==0 && h==0) {
				break;
			}
			
			arr = new int[h][w];
			
			for(int i=0; i<arr.length; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<arr[0].length; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			int count = 0;
			for(int i=0; i<arr.length; i++) {
				for(int j=0; j<arr[0].length; j++) {
					if(arr[i][j]==1) {
						count++;
						to.getIsland(arr, new Dot(i, j));
					}
				}
			}
			System.out.println(count);
			count=0;
		}
	}
	
	public void getIsland(int[][] arr, Dot Dot) {
		Queue<Dot> q = new LinkedList<Dot>();
		q.add(Dot);
		arr[Dot.x][Dot.y] = 0;
		
		int curX;
		int curY;
		int nextX;
		int nextY;
		Dot d;
		
		while(!q.isEmpty()) {
			d = q.poll();
			curX = d.x;
			curY = d.y;
			
			for(int i=0; i<8; i++) {
				nextX = curX+nX[i];
				nextY = curY+nY[i];
				
				if(nextX<0 || nextY<0 || nextX>=arr.length ||nextY>=arr[0].length) {
					continue;
				}
				if(arr[nextX][nextY]==1) {
					arr[nextX][nextY]=0;
					q.add(new Dot(nextX, nextY));
				}
			}
		}
		
	}
}
class Dot{
	int x;
	int y;
	
	public Dot(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

---

맨 위의  static 배열인 nX, nY 배열은 처음 도착한 섬에서부터 주위의 8방향을 탐색하기 위해 만들어 놓았습니다.

그리고 메인메소드는 while문을 계속 돌리면서 입력형식에 맞게 받다가

너비와 높이가 0이 되는 순간 break를 걸어줬습니다.

그리고 각각의 지도가 생성될때마다 지도의 처음부터 끝까지 섬을 탐색합니다.

섬이 탐색되는 순간 BFS를 하기 위해 getIsland 메소드를 호출하고 count를 1 늘립니다.

그리고 지도의 섬이 모두 탐색되면 다시 다음 지도를 위해 count를 0으로 초기화.

getIsland 메소드는  BFS를 하기 위해 큐를 생성해주고 섬의 좌표값을 넣으며 1을 0으로 바꿔줍니다.

(이 부분의 방문했는지 안했는지의 배열은 따로 생성하지 않았습니다.)

위의 선언된 다음 좌표값을 넣으며 경계선 체크를 해주고 경계선을 넘어가버린다면 ( 0,과 배열의 크기부분) continue,

그리고 넘지 않으면서 주위가 1이라면(연결된 섬일경우) 그부분을 0으로 바꾸고 큐에 넣으면서 BFS를 진행시켰습니다.

---

대충 적긴 했는데 좀 다시 글 쓰는것에 해이해지는거 같아 러프하게 적기라도 했습니당.

코드 적기전에 생각은 금방 했는데 왜캐 손으로 옮기는데 오래걸리는지...  지저분하기도 하고... 힝 ㅜ