[백준 알고리즘 - 4963] 섬의개수(bfs) - java

2018.06.30 네이버 블로그에 작성된 글

미로찾기랑 비슷한 문제였다

---

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다.

---

모든 Land를 다 밟을 때까지 bfs를 수행하는 것

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub		
		Scanner scan=new Scanner(System.in);
		int w, h;
		
		while(true) {
			w= scan.nextInt();//너비
			h=scan.nextInt();//높이
		
			if(w==0 && h==0) return;//입력 종료 조건
		
			Area[][] matrix=new Area[h][w];
		
		
			Queue<Area> areaData=new LinkedList<>();//모든 land 를 담을 queue
		    //Land를 다 밟긴 해야하니까 일단 때려넣는다 
		
			for(int i=0; i<h; i++)
				for(int j=0; j<w;j++)
				{
					int n=scan.nextInt();
					matrix[i][j]=new Area();
					if(n==1) {					
						matrix[i][j].isMoveable=true;
						areaData.add(matrix[i][j]);//모든 이동 가능한 land를 담는 변수		
				}else {
					matrix[i][j].isMoveable=false;
				}
				matrix[i][j].x=i;
				matrix[i][j].y=j;
			}
		

		int count=0;//섬의 개수를 세는 변수 
	
		Queue<Area> queue=new LinkedList<>();//방문 할 land를 담는 queue -> bfs 
            
		queue.add(areaData.poll());//첫 번째 land 위치 queue에 삽입 
		
		while(queue.peek()!=null) {//방문할 land가 남아있다면 
			int x= queue.peek().x;
			int y=queue.peek().y;
            
            //1. 모든 상하좌우, 대각선이 checked 되어있다면, 현재 land 또한 그 섬의 일부 -> count 하지 않음
			if(queue.peek().checked==false) {//아직 check 안되어있는 land 라면
				//위쪽 land가 이미 방문 되어있는지
				if(x-1 >=0 && matrix[x-1][y].isMoveable==true && matrix[x-1][y].checked==true){}
				//위 왼쪽 대각선 land가 이미 방문 되어있는지
				else if(x-1 >=0 && y-1 >=0 && matrix[x-1][y-1].isMoveable==true && matrix[x-1][y-1].checked==true){}
				//위 오른쪽 대각선 land가 이미 방문 되어있는지
				else if(x-1 >=0 && y+1 < w && matrix[x-1][y+1].isMoveable==true && matrix[x-1][y+1].checked==true){}
				//왼쪽 land가 이미 방문 되어있는지
				else if(y-1 >= 0 && matrix[x][y-1].isMoveable==true && matrix[x][y-1].checked==true ) {}
				//오른쪽 land가 이미 방문 되어있는지
				else if(y+1<w && matrix[x][y+1].isMoveable==true && matrix[x][y+1].checked==true) {}
				//왼쪽 아래 대각선 land가 이미 방문 되어있는지
				else if(y-1>=0 && x+1<h && matrix[x+1][y-1].isMoveable==true && matrix[x+1][y-1].checked==true){}
				//아래쪽 land가 이미 방문 되어있는지
				else if(x+1<h && matrix[x+1][y].isMoveable==true && matrix[x+1][y].checked==true) {}
				//오른쪽 아래 대각선 land가 이미 방문 되어있는지 
				else if(y+1 < w && x+1 <h && matrix[x+1][y+1].isMoveable==true && matrix[x+1][y+1].checked==true) {}
				
                else //주변 모든 land가 방문되어있지 않고, 현재 자신도 방문되어있지 않다면 섬의 시작
					count++;//섬의 개수 카운트
				queue.peek().checked=true; //방문 표시하고 
			}
            
            //현재 위치에서 방문 가능한 land 체크
				//위쪽으로 방문 가능한지
				if(x-1 >=0 && matrix[x-1][y].isMoveable==true && matrix[x-1][y].checked==false)
				{
					matrix[x-1][y].checked=true;//위쪽 land check
					queue.add(matrix[x-1][y]);//다음에 이동하기 위해 queue에 삽입
				}
				else if(y-1 >= 0 && matrix[x][y-1].isMoveable==true && matrix[x][y-1].checked==false ) {
					matrix[x][y-1].checked=true;
					queue.add(matrix[x][y-1]);
				}
				//위 왼쪽 대각선으로 방문 가능한지
				if(x-1 >=0 && y-1 >=0 && matrix[x-1][y-1].isMoveable==true && matrix[x-1][y-1].checked==false)
				{
					matrix[x-1][y-1].checked=true;
					queue.add(matrix[x-1][y-1]);
				}
				//위 오른쪽 대각선으로 방문 가능한지
				if(x-1 >=0 && y+1 < w && matrix[x-1][y+1].isMoveable==true && matrix[x-1][y+1].checked==false)
				{
					matrix[x-1][y+1].checked=true;
					queue.add(matrix[x-1][y+1]);
				}
				//오른쪽으로 방문 가능한지
				if(y+1<w && matrix[x][y+1].isMoveable==true && matrix[x][y+1].checked==false) {
					matrix[x][y+1].checked=true;//방문 표시 
					queue.add(matrix[x][y+1]);
				}
				//왼쪽 아래 대각선으로 방문 가능한지
				if(y-1>=0 && x+1<h && matrix[x+1][y-1].isMoveable==true && matrix[x+1][y-1].checked==false) {
					matrix[x+1][y-1].checked=true;
					queue.add(matrix[x+1][y-1]);
				}
				//아래쪽으로 방문 가능한지
				if(x+1<h && matrix[x+1][y].isMoveable==true && matrix[x+1][y].checked==false) 					{
					matrix[x+1][y].checked=true;
					queue.add(matrix[x+1][y]);
				}
				//오른쪽 아래 대각선으로 방문 가능한지 
				if(y+1 < w && x+1 <h && matrix[x+1][y+1].isMoveable==true && matrix[x+1][y+1].checked==false) {
					matrix[x+1][y+1].checked=true;
					queue.add(matrix[x+1][y+1]);
				}
			
			
			//모든 처리 마치고 해당 land queue에서 제거
				queue.poll();
				if(queue.peek()==null) {//떨어져있는 land를 체크하기 위해 areaData에서 다음 위치를 꺼내옴
					while(areaData.peek()!=null && areaData.peek().checked==true)//단, 이미 방문한 land 제외
                        areaData.poll();
                    queue.add(areaData.poll());
				}
		}
		
		System.out.println(count);
		}

	}

}

class Area{
	int x,y;
	boolean isMoveable;//이동 가능한 곳인지 -> Land인지?
	boolean checked=false;//이동 가능 체크했는지?
}

막 어려운건 아니었는데 경우의 수가 너무 많아 코드가 더러워서 풀면서도 내가 맞게 푸는건지 의문이었당