4963번

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

4963번: 섬의 개수

오늘 풀은 문제는 간단한 BFS문제였다. 풀었던 문제들과 같은 유형이여서 1트만에 풀어냈다.

단지번호 붙이기 문제와도 비슷하다.

 

BFS로직은 같고 인접리스트를 상하좌우, 대각선으로 해서 탐색을 진행하면 된다.

 

전체 테이블을 탐색하면서 섬이 있으면 섬의 면적 전체를 방문처리한다. 그리고 다음 섬을 탐색하는 식으로 전체 테이블을 탐색한다.

섬의 수를 세는 로직은 아래와 같다.

for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
        if(table[i][j]==1){
            g.bfs(j,i);
            count++;
        }
    }
}

인접 리스트는 아래와 같은 int형 배열로 구성한다.

int[] dx = {1,0,-1, 0,1, 1,-1,-1};
int[] dy = {0,1, 0,-1,1,-1, 1,-1};

그리고 BFS 로직은 아래처럼 섬을 방문처리하고 인접한 섬의 면적 또한 방문처리하게 구현한다.

로직에서 주의 할 것은 테이블의 범위를 벗어나지 않게 만들어야 하기 때문에 범위를 조건으로 준다.

public void bfs(int Rx, int Ry){
    queue.add(new Node(Rx,Ry));
    table[Ry][Rx]=0;
    while (!queue.isEmpty()){
        Node tmp = queue.poll();
        for(int i=0; i<8; i++){
            int x = tmp.x+dx[i];
            int y = tmp.y+dy[i];
            if(x>=0 && y>=0 && x<w && y<h && table[y][x]==1){
                queue.add(new Node(x,y));
                table[y][x]=0;
            }
        }
    }
}

 

정답은 아래 코드와 같다.

package backjoon.b4963;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class b4963 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while (true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            if(w==0&&h==0){
                break;
            }
            int[][] table = new int[h][w];
            for(int i=0; i<h; i++){
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<w; j++){
                    table[i][j]= Integer.parseInt(st.nextToken());
                }
            }
            Graph g = new Graph(w,h,table);
            int count = 0;
            for(int i=0; i<h; i++){
                for(int j=0; j<w; j++){
                    if(table[i][j]==1){
                        g.bfs(j,i);
                        count++;
                    }
                }
            }

            sb.append(count).append("\n");
        }
        System.out.println(sb);
    }
}
class Graph{
    int w;
    int h;
    int[] dx = {1,0,-1, 0,1, 1,-1,-1};
    int[] dy = {0,1, 0,-1,1,-1, 1,-1};
    Queue<Node> queue;
    int[][] table;
    public Graph(int w, int h, int[][] table) {
        this.queue = new LinkedList<>();
        this.table=table;
        this.h=h;
        this.w=w;
    }

    public void bfs(int Rx, int Ry){
        queue.add(new Node(Rx,Ry));
        table[Ry][Rx]=0;
        while (!queue.isEmpty()){
            Node tmp = queue.poll();
            for(int i=0; i<8; i++){
                int x = tmp.x+dx[i];
                int y = tmp.y+dy[i];
                if(x>=0&&y>=0&&x<w&&y<h&&table[y][x]==1){
                    queue.add(new Node(x,y));
                    table[y][x]=0;
                }
            }
        }
    }
}
class Node{
    int x;
    int y;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}