[백준] 알고리즘 분류(트리,JAVA)4963번, 섬의 개수

문제 링크

4963번: 섬의 개수

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 0 0의 h와 w를 받으면 테스트케이스가 종료됩니다.

2. 정사각형마다 가로, 세로, 대각선으로 연결된 것은 같은 섬으로 봅니다.

3. 1은 땅, 0은 바다로 표현합니다.

4. 각 테스트케이스마다 섬의 개수를 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. BFS로 가로, 세로, 대각선으로 섬의 개수가 몇 개인지 탐색합니다.

 

3. 섬의 개수를 결과로 출력합니다.

 

공간 이동.

 

(-1, -1)	(-1, 0)	(-1, 1)
(0, -1)	현재	(0, 1)
(1, -1)	(1, 0)	(1, 1)

공간을 이동하는 방법은 위에 표와 같은 8가지가 존재합니다.

 

 

예제입력 1.

※테스트케이스 4번만 진행되는 과정을 보여드리겠습니다.

 

1. 입력된 정보를 저장합니다.

 

h : 5

w : 4

1	0	1	0	0
1	0	0	0	0
1	0	1	0	1
1	0	0	1	0

 

2. BFS로 가로, 세로, 대각선으로 섬의 개수가 몇 개인지 탐색합니다.

 

BFS탐색을 할 때 섬이 방문하지 않았던 땅들을 탐색합니다.

 

(0, 0)인 땅 BFS 탐색.

1	0	1	0	0
1	0	0	0	0
1	0	1	0	1
1	0	0	1	0

 

(0, 2)인 땅 BFS 탐색.

1	0	1	0	0
1	0	0	0	0
1	0	1	0	1
1	0	0	1	0

 

(2, 2)인 땅 BFS 탐색.

1	0	1	0	0
1	0	0	0	0
1	0	1	0	1
1	0	0	1	0

 

섬의 개수 : 3개

 

3. 섬의 개수를 결과로 출력합니다.

 

3을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 지도에 정보를 띄어쓰기 기준으로 나누었습니다.
• bfs함수를 사용하여 각 테스트 케이스의 섬의 개수를 구하였습니다.
• 섬의 개수들을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 BFS탐색을 통해 주변 공간을 탐색하여 섬을 방문합니다.
• mapCheck은 공간을 이동할 때 지도에 벗어나는지 확인하는 함수입니다.

 

import java.io.*;
import java.util.*;


public class Main {
    //현재 정사각형의 위치를 나타내는 클래스
    static class position{
        int x, y;
        public position(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static int[][] map;		//땅 , 바다 정보 저장 배열
    //가로, 세로, 대각선 움직이는 X변경값
    static int[] dx = {-1, 0, 1, -1, 1, -1, 0, 1};
    //가로, 세로, 대각선 움직이는 Y변경값
    static int[] dy = {-1, -1, -1, 0, 0, 1, 1, 1};
    static boolean[][] visited;		//땅 방문 확인 배열
    static int index, w, h;
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        //각 테스트케이스 진행
        while(true){
            st = new StringTokenizer(br.readLine()," ");
            //w, h 저장
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            if(w == 0 && h == 0)
                break;
            map = new int[h][w];
            visited = new boolean[h][w];
            index = 1;
            //땅, 바다 정보 저장
            for(int i=0;i<h;i++){
                st = new StringTokenizer(br.readLine()," ");
                for(int j=0;j<w;j++)
                    map[i][j] = Integer.parseInt(st.nextToken());
            }
            //BFS 탐색 진행
            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++)
                    //해당 정사각형이 땅이고 방문한 곳이 아닌 경우 탐색 진행
                    if(!visited[i][j] && map[i][j] == 1){
                        bfs(i, j);		//BFS 탐색
                        index++;		//섬의 개수 증가
                    }
            }
            bw.write((index-1) + "\n");	//현재 테스트케이스 섬의 개수 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS탐색을 진행하는 함수
    static void bfs(int y, int x){
        Queue<position> q = new LinkedList<>();
        q.add(new position(x, y));
        while(!q.isEmpty()){
            position cur = q.poll();
            //가로, 세로, 대각선 주변 탐색
            for(int i=0;i<8;i++){
                int tempX = cur.x + dx[i];
                int tempY = cur.y + dy[i];
                //지도에 벗어나지 않고, 방문하지 않았으며 땅인 경우
                if(mapCheck(tempX,tempY) && !visited[tempY][tempX] && map[tempY][tempX] == 1){
                    visited[tempY][tempX] = true;
                    q.add(new position(tempX,tempY));
                }
            }
        }
    }
    //공간 이동 시 지도에 벗어나는지 확인하는 함수
    static boolean mapCheck(int x, int y){
        //공간에 벗어나지 않았을 때
        if(x >= 0 && y >= 0 && x < w && y < h)
            return true;
        return false;
    }
}