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

[백준] 섬의 개수 4963번

나의 풀이

public class NumberOfIslands {
    static int[][] graph;
    static int w, h;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        while(true) {
            int answer = 0;
            graph = new int[50][50];
            st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            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++) {
                    graph[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for(int x = 0; x < h; x++) {
                for(int y = 0; y < w; y++) {
                    if(dfs(x, y) == true) {
                        answer++;
                    }
                }
            }

            sb.append(answer).append("\n");
        }

        System.out.println(sb);
    }

    private static boolean dfs(int x, int y) {
        if(x < 0 || y < 0 || x >= h || y >= w) {
            return false;
        }

        if(graph[x][y] == 1) {
            graph[x][y] = 0;

            dfs(x - 1, y); //상
            dfs(x + 1, y); //하
            dfs(x, y - 1); //좌
            dfs(x, y + 1); //우
            dfs(x - 1, y - 1); //좌상
            dfs(x + 1, y - 1); //좌하
            dfs(x - 1, y + 1); //우상
            dfs(x + 1, y + 1); //우하

            return true;
        }

        return false;
    }
}

• dfs를 사용하여 접근하였다.
• 우선 상, 하, 좌, 우 뿐 아니라 대각선의 위치도 고려해야 한다. 그리고 0 0 이 입력될 떄 까지 무한 반복을 해야 하기 때문에 while(true)로 시작하였다.
• 반복이 한 턴 끝날 때 마다 그래프와 answer는 초기화 되야하기 때문에 그래프의 초기화를 while문 안에 두었다.
• 만약 입력되는 w 와 h의 값 모두 0이라면 반복은 종료된다.
• 모두 0이 아니라면 입력되는 값을 graph에 입력해준다.
• graph를 돌면서, 좌표들을 dfs를 통해서 검증한다. dfs를 통해서 true가 리턴된다면 그 때 answer 을 1 증가시킨다.
• dfs는 만약 입력된 좌표가 w, h의 범위를 벗어나면 false를 리턴한다.
• 입력된 좌표의 graph 값이 0이 아닌 1이라면, 상, 하, 좌, 우 모든 대각선을 탐색하고 탐색을 마치면 true 를 리턴한다. 이 때, 탐색을 마친 좌표의 값은 0으로 바꿔주어서 중복 탐색하는 일을 없게 만들어야 한다.
• graph의 값이 1이 아니라면 if문을 타지 않고 false를 리턴한다.
• 해당 반복 종료 후, answer의 값을 스트링 빌더에 넣어준다.
• 모든 반복이 종료되면, 스트링 빌더의 값을 출력해준다.