[백준] 4963 섬의 개수 - Graph Theory / Java

• 문제 링크

4963번: 섬의 개수

 

• 풀이 과정

[백준] 11724 연결 요소의 개수 - Graph Theory / Java

위의 문제와 유사한 연결 요소의 개수를 구하는 문제.

다른 점은 2차원 배열에서 탐색을 진행하며 bfs 로 풀이하였다.

 

탐색할 방향은 대각선도 포함이므로 8방향 탐색을 위한 dy, dx 배열을 미리 생성해둔다.

각 테스트 케이스를 while 문에서 연속하여 수행하고 w, h 값이 0일 시 반복문을 탈출한다.

 

2차원 배열 map 에서 섬에 해당하는 노드의 값은 1, 바다는 0 이며

전체 노드를 탐색하는 중 현재 노드의 값이 1 일 경우 해당 노드를 시작점으로써 bfs 탐색을 수행하며

연결 요소의 개수를 의미하는 cnt 변수에 1을 더한다.

 

8방향으로 연결된 모든 노드를 탐색하고 방문한 노드마다 0으로 값을 변경하여 방문했음을 표시한다.

이렇게 하나의 연결 요소의 탐색을 끝마치고 bfs 함수를 빠져나오며,

아직 값이 1인 노드를 찾아 새로운 연결 요소로써 탐색 및 cnt 변수에 1을 더한다.

 

이렇게 각 라인마다 테스트 케이스의 모든 연결 요소의 개수가 정답으로써 출력된다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		while (true) {
			st = new StringTokenizer(br.readLine());
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());

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

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

			int cnt = 0;
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (map[i][j] == 0)
						continue;

					bfs(i, j);
					cnt++;
				}
			}

			bw.write(cnt + "\n");
		}

		bw.flush();
	}

	private static void bfs(int y, int x) {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(y, x));
		map[y][x] = 0;

		while (!q.isEmpty()) {
			Node now = q.poll();
			for (int i = 0; i < 8; i++) {
				int ny = now.y + dy[i];
				int nx = now.x + dx[i];

				if (ny < 0 || nx < 0 || ny >= h || nx >= w)
					continue;
				if (map[ny][nx] == 0)
					continue;

				q.offer(new Node(ny, nx));
				map[ny][nx] = 0;
			}
		}
	}

	private static class Node {
		int y;
		int x;

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

}