[Java] 백준 4963 : 섬의 개수

문제 링크

1.

많이 풀어 봤던 기본적인 그래프 문제. 유기농 배추 문제와 매우 유사해서 쉽게 풀었다.

 

테스트 케이스는 다 맞고, 전혀 틀린 부분이 없는데 오답처리가 나길래 골치가 아팠다. 원인은 내가 잠시 수정했던 범위였는데 이런 어이없는 실수는 하지 않도록 주의하자.

 

 

2.

풀이는 유기농 배추 문제를 참고하면 될 것 같다. (링크 걸어 놓았음)

단, 이 문제에서는 4 방향이 아닌 8 방향을 모두 검사하여야 한다.

 

3.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int w, h;
    static int[][] area;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        while (true) {
            w = sc.nextInt();
            h = sc.nextInt();

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

            area = new int[h][w];
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    area[i][j] = sc.nextInt();
                }
            }

            int answer = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (area[i][j] == 1) {
                        bfs(i, j);
                        answer++;
                    }
                }
            }
            System.out.println(answer);
        }
        sc.close();
    }

    static void bfs(int x, int y) {
        Queue<Pos> q = new LinkedList<>();
        int[] dx = { -1, -1, 0, 1, 1, 1, 0, -1 };
        int[] dy = { 0, 1, 1, 1, 0, -1, -1, -1 };

        area[x][y] = 2;
        q.offer(new Pos(x, y));

        while (!q.isEmpty()) {
            Pos temp = q.poll();

            for (int i = 0; i < 8; i++) {
                int nx = dx[i] + temp.x;
                int ny = dy[i] + temp.y;

                if (0 <= nx && nx < h && 0 <= ny && ny < w) {
                    if (area[nx][ny] == 1) {
                        area[nx][ny] = 2;
                        q.offer(new Pos(nx, ny));
                    }
                }
            }
        }
    }
}

class Pos {
    int x, y;

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

 

 

4.

none