[백준] 4963번 섬의 개수 JAVA (자바) 풀이

문제 4963번

 :  섬의 개수를 세는 프로그램

 :  정사각형으로 이루어져 있는 섬과 바다 지도

 :  붙어있는 땅이면 가로, 세로, 대각선 이동가능 = 하나의 섬

 

 

  섬 개수 = 3

 

 

 

 

 [입력]

 :  너비 w, 높이 h

 :  h개 줄만큼 지도 표시 (1 = 땅, 0 = 바다)
 :  위의 과정 반복

 :  맨 마지막 줄에는 0 0

 

 

 [출력]

 :  각 테스트 케이스의 섬의 개수를 출력

 

 

 [설명]

 

 BFS 

 

 

 현재 정점에 연결된 가까운 점들부터 탐색

 

 Queue를 사용해서 구현

 

 

 

 

 java.awt.Point 

 

-  Point 클래스는 좌표 상의 위치를 나타내는데 사용

-  x와 y좌표값을 저장하기 위한 멤버변수를 갖는다

 

Field Summary
Modifier and Type	Field and Description	설명
int	x	x좌표
int	y	y좌표

메소드	설명
void setLocation(int x, int y)	x, y좌표의 위치값을 설정
Point getLocation()	현재 위치의 x, y좌표값을 반환

출처 : https://codedragon.tistory.com/6044

 

 

 [BFS 코드]

import java.io.*;
import java.awt.Point;
import java.util.*;
public class Main{
    static int w, h;
    static int arr[][];
    static boolean visit[][];
    static Queue<Point> q = new LinkedList<>();
    static int dx[] = {0, 0, -1 ,1, -1, 1, -1, 1};
    static int dy[] = {-1, 1, 0, 0, 1, 1, -1, -1};
    
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        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];
           visit= new boolean[h][w];
        
           for(int i =0; i<h; i++){
               st = new StringTokenizer(br.readLine());
               for(int j=0; j<w; j++){
                    arr[i][j]= Integer.parseInt(st.nextToken());
               }
           }
            int count=0;

            for(int i =0; i<h; i++){
                for(int j=0; j<w; j++){
                    if(visit[i][j] == false && arr[i][j]==1){
                        bfs(i,j);
                        count ++;
                    }
                }
            }
            System.out.println(count);
        }
    }  
        
    public static void bfs(int x, int y){
        q.add(new Point(x,y));
        visit[x][y]=true;
            
        while(!q.isEmpty()){
            Point p = q.poll();
            for(int i=0;i<8;i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if(nx >=0 && ny >=0 && nx <h && ny < w){
                    if(visit[nx][ny] == false && arr[nx][ny] == 1){
                        q.add(new Point(nx,ny));
                        visit[nx][ny] = true;
                    }
                }
            }
        }
    }
}

 

 [해설]
     

 :  import java.awt.Point;

 

 :  static int w, h;  너비 높이 (입력 첫째줄)
    static int arr[][];  땅위치 
    static boolean visit[][];  방문처리
    static Queue<Point> q = new LinkedList<>();  큐생성
    static int dx[] = {0, 0, -1 ,1, -1, 1, -1, 1};  (dx,dy) 좌표로 볼 것
    static int dy[] = {-1, 1, 0, 0, 1, 1, -1, -1};  상,하,좌,우,대각선 4개

 

 

:  while(true){  별다른 종료 없을 때까지 계속돌아간다

 

       st=new StringTokenizer(br.readLine());  한 줄 입력받기
       w =Integer.parseInt(st.nextToken());  너비
       h =Integer.parseInt(st.nextToken());  높이
            
       if(w==0 && h==0) break;  마지막줄 w, h에 0, 0 들어올 때 while문 종료
         

       arr= new int[h][w];  땅 위치 배열 (h,w 자리 헷갈리지 말 것)
       visit= new boolean[h][w];  방문기록 배열 
        
       for(int i =0; i<h; i++){  높이 배열부터 만들기 시작
            st = new StringTokenizer(br.readLine());  다음줄 끊어읽기
            for(int j=0; j<h; j++){  너비 배열 만들기 시작
                 arr[i][j]= Integer.parseInt(st.nextToken());  입력받은 숫자들 배열 안에 넣기
            }                                                                      1이면 땅이다
       }

 

      int count = 0; 초기화 해주는 위치 중요해요 이것때문에 계속 오류가 났어요
       

       for(int i =1; i<h; i++){  높이 배열부터 시작
            for(int j=0; j<w; j++){  너비 배열 시작
                if(visit[i][j]==false && arr[i][j]==1){  방문기록은 없고 땅이 1표시있음 bfs처리
                    bfs(i,j);  해당하는 땅의 배열을 bfs에 그대로 대입
                    count ++;  땅 발견했으니 하나의 섬으로 카운트하기
                }
            }
       }
       System.out.println(count);  결과출력

   }
         
        
:  public static void bfs(int x, int y){  초기값은 [i][j] 이다!
        q.add(new Point(x,y));  현 (x,y)좌표 큐에 추가 
        visit[x][y]=true; 해당 위치 방문처

        while(!q.isEmpty()){  큐 빌 때까지 빼기
              Point p = q.poll();  큐에 넣은 x,y 좌표 빼서 p에 저장하기

              for(int i=0;i<8;i++){  갈 수 있는 8개 방향 모두 탐색 (상, 하, 좌, 우, 대각선)
                    int nx = p.x + dx[i];  새로 이동할 x 좌표 = 큐에서 빼온 현재 x값 + 갈 수 있는 x 방향
                    int ny = p.y + dy[i];  새로 이동할 y 좌표 = 큐에서 빼온 현재 y값 + 갈 수 있는 y 방향

                 

                    if(nx >=0 && ny >=0 && nx <h && ny < w){  지도 arr 배열이 [0,0] ~ [w,h] 까지라서
                        if(visit[nx][ny] == false && arr[nx][ny] == 1){  새로운 좌표 = 1이고 방문처리 X일 경우
                            visit[nx][ny] = true;  해당 좌표 방문처리해주고
                            q.add(new Point(nx,ny));  큐에 해당 좌표 넣어주기
                        }
                    }
              }
         }       

   }

 

 

* 처음에 입력을 w받고 h받고 배열 순서는 arr[h][w] 했어서 

   bfs에서 입력받은 nx, ny도 arr[ny][nx]로 생각하실 수 있는데 헷갈리지 마세요

   arr[ny][nx]든 arr[nx][ny]든 아무런 상관이 없습니다 다만 처음 지정해놓은 배열의 단위가 arr[h][w] 이므로

   arr의 앞자리는 h보다 작고 뒷자리는 w보다 작아야해요

   arr[ny][nx] 이면 =>  범위는 nx <w && ny < h          /         arr[nx][ny] 이면 =>  범위는 nx <h && ny < w

 

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

 

 

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

 

4963번: 섬의 개수

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *