[Baekjoon] 백준 4963 섬의갯수 (S2^ / BFS) - Java

링크

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

4963번: 섬의 개수

 

 

 

문제 해석

각 테스트 케이스에서 섬의 개수 구하기

하나의 섬은 가로, 세로, 대각선으로 인접하여 연결된 것을 기준으로 함 

 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {

	static int[][] map;
	static int answer; // 섬의 개수 기록
	static int[] dx = { 0, -1, -1, -1, 0, 1, 1, 1 };
	static int[] dy = { -1, -1, 0, 1, 1, 1, 0, -1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		while (true) {
			st = new StringTokenizer(br.readLine());

			int w = Integer.parseInt(st.nextToken());
			int h = Integer.parseInt(st.nextToken());

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

			map = new int[h][w];

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

			answer = 0;
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (map[i][j] == 1) {
						bfs(i, j);
					}
				}
			}
			System.out.println(answer);
		} // [E] while
	}

	static class Point {
		int x;
		int y;

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

	private static void bfs(int x, int y) {
		Queue<Point> q = new LinkedList<>();

		q.offer(new Point(x, y));
		map[x][y] = 0;

		while (!q.isEmpty()) {
			Point p = q.poll();

			for (int i = 0; i < dx.length; i++) {
				int cx = p.x + dx[i];
				int cy = p.y + dy[i];

				if (cx >= 0 && cx < map.length && cy >= 0 && cy < map[0].length 
				&& map[cx][cy] == 1) {
					map[cx][cy] = 0;
					q.offer(new Point(cx, cy));
				}
			}
		}
		answer++;
	}
}

 

 

 

코드 해석

BFS 기본 문제입니다.

 

기존의 단지번호붙이기 등과 다르게 대각선이 기준에 포함되어 있으므로, 8방 탐색을 수행해야 합니다.

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice