(Java/자바) - 백준(BOJ) 4963번 : 섬의 개수

 

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

4963번: 섬의 개수

---

• 문제 : 

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

 

 

 

---

• 풀이 :

그래프 탐색 기본 문제입니다.

 

BFS, DFS 등 그래프 탐색 방법으로 해결이 가능합니다.

 

저는 BFS를 사용해서 풀었습니다.

 

1. 테스트 케이스의 개수가 정해지지 않았으므로 while(true)만큼 반복하며 인풋 중 w와 h값이 둘다 0일 때 종료합니다.

 

2. 각 실행마다 board를 입력받고 순회하면서 땅인 부분을 만났을 때 상하좌우 대각선 총 8방위의 방향을 탐색하는

bfs를 실행합니다.

 

3. 기존 bfs에서 사용하는 visited를 사용하지 않고 탐색할 때 board의 값을 1(땅) -> 0(바다)로 바꿔주어 중복탐색을 방지하였습니다.

 

4. 모든 좌표를 순회하면서 bfs를 총 몇 번 호출했는지 카운트하여 출력합니다. 

 

---

• 소스코드 : 

import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Queue;
import java.io.*;

public class Main{
	
//	좌표의 쌍
	static class Node {
		int x,y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
//	bfs로 이동 가능한 섬 탐색
	static int[][] bfs(int x, int y, int[][] board) {
		int[] dx = {-1,1,0,0,-1,1,-1,1};
		int[] dy = {0,0,-1,1,1,-1,-1,1};

		Queue<Node> q = new LinkedList<Node>();
		q.add(new Node(x,y));
		board[x][y] = 0;
		while (!q.isEmpty()) {
			Node curr = q.poll();
			for (int i = 0; i < 8; i++) {
				int ax = curr.x + dx[i];
				int ay = curr.y + dy[i];
				if (0 <= ax && ax < board.length && 0 <= ay && ay < board[0].length && board[ax][ay] == 1) {
					q.add(new Node(ax,ay));
					board[ax][ay] = 0;
				}
			}
		}
		return board;
	}
	
	public static void main(String[] args) throws Exception {
		int w,h,answer;
		int[][] board;
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while(true) {
			answer = 0;
			StringTokenizer st = new StringTokenizer(br.readLine());
			h = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());
			
//			종료조건
			if (w == 0 && h == 0) return;
			
			board = new int[w][h];
			for (int i = 0; i < w; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < h; j++) {
					board[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
//			bfs 실행
			for (int i = 0; i < w; i++) {
				for (int j = 0; j < h; j++) {
					if (board[i][j] == 1) {
						board = bfs(i,j, board);
						answer++;
					}
				}
			}
			System.out.println(answer);
		}
	}
}