백준 4963 섬의 개수

백준 4963 섬의 개수

1. 문제 링크

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

4963번: 섬의 개수

 

2. 문제 해결에 대한 아이디어

1. Input으로 받은 2차원 배열을 순회하면서 1로 되어 있는 위치에서 BFS를 수행한다.

2. BFS를 수행한 카운트를 출력한다.

3. 대각선도 접근할 수 있는 것을 간과하면 안 된다.

 

3. 코드

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

public class Main {
	static int W, H;
	static int[][] board;
	static boolean[][] visited;
	static int count;
	static int[] dirY = { 0, 0, 1, -1, 1, 1, -1, -1 };
	static int[] dirX = { 1, -1, 0, 0, 1, -1, 1, -1 };
	static Queue<Pair> q;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			String[] wh = br.readLine().split(" ");
			W = Integer.parseInt(wh[0]);
			H = Integer.parseInt(wh[1]);

			if (W == 0 && H == 0)
				return;

			board = new int[H][W];
			visited = new boolean[H][W];
			q = new LinkedList<>();
			count = 0;

			for (int i = 0; i < H; i++) {
				String[] lines = br.readLine().split(" ");
				for (int j = 0; j < W; j++) {
					board[i][j] = Integer.parseInt(lines[j]);
					if (board[i][j] == 1)
						q.add(new Pair(i, j));
				}
			}

			while (!q.isEmpty()) {
				Pair target = q.poll();
				if (visited[target.y][target.x])
					continue;
				BFS(target);
				++count;
			}

			System.out.println(count);
		}
	}

	public static void BFS(Pair p) {
		Queue<Pair> tq = new LinkedList<>();
		tq.add(p);

		while (!tq.isEmpty()) {
			Pair now = tq.poll();
			int x = now.x;
			int y = now.y;
			for (int i = 0; i < 8; i++) {
				int yy = y + dirY[i];
				int xx = x + dirX[i];
				if (xx < 0 || yy < 0 || xx >= W || yy >= H || visited[yy][xx] || board[yy][xx] != 1)
					continue;
				tq.add(new Pair(yy, xx));
				visited[yy][xx] = true;

			}
		}
	}

}

class Pair {
	public int y, x;

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

}

 

4. 채점 결과

 

5. 느낀 점

1. 기본적인 BFS 문제에서 대각선 방향까지 고려하는 문제였다.