[Java] 백준 - 4963번: 섬의 개수

7월 21일(금) - 그래프와 순회 (4963번)

4963번: 섬의 개수

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

(C언어 풀이 활용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class Main {
    static int w,h;
    static int[][] map;
    static int[][] visited;
    static int dx[] = { -1,-1,-1,0,0,1,1,1 };
    static int dy[] = { 0,-1,1,-1,1,0,-1,1 };

    static void dfs(int y, int x){
        visited[y][x] = 1;

        for(int i=0; i<8; i++)
        {
            int next_x = x + dx[i];
            int next_y = y + dy[i];

            if(next_x<0 || next_y<0 || next_x>=w || next_y>=h)
            {
                continue;
            }
            if(map[next_y][next_x] == 1 && visited[next_y][next_x] == 0)
            {
                dfs(next_y,next_x);
            }
        }
    }

    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());

            map = new int[h][w];
            visited = new int[h][w];
            for(int i=0; i<h; i++)
            {
                for(int j=0; j<w; j++)
                {
                    map[i][j] = 0;
                    visited[i][j] = 0;
                }
            }

            if(w==0 && h==0)
            {
                break;
            }

            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());
                }
            }

            int count=0;
            for(int i=0; i<h; i++)
            {
                for(int j=0; j<w; j++)
                {
                    if (map[i][j] == 1 && visited[i][j] == 0)
                    {
                        dfs(i,j);
                        count++;
                    }
                }
            }

            System.out.println(count);
        }
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ