[백준] [4963] 섬의 개수 (BFS)

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

4963번: 섬의 개수

---

문제

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

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

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

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

예제 입력 1 복사

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

예제 출력 1 복사

0
1
1
3
1
9

---

※ JAVA 코드 (섬의 개수)

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

public class Main {
	
	static int w, h;
	static int[][] map;
	static boolean[][] visited;
	
	// 땅 : 1, 물 : 0
	static final int LAND = 1;
	static final int WATER = 0;
	
	// 대각, 상하좌우
	static int[] dx = {-1, -1, -1, 0, 1, 1,  1,  0};
	static int[] dy = {-1,  0,  1, 1, 1, 0, -1, -1};
	
	static class Node{
		int x, y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static void BFS(int x, int y) {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(x, y));
		visited[x][y] = true;
		
		// 큐가 빌때까지 반복
		while(!q.isEmpty()) {
			Node now = q.poll();
			int nowX = now.x;
			int nowY = now.y;
			
			for(int i = 0; i < 8; i++) {
				int nextX = nowX + dx[i];
				int nextY= nowY + dy[i];
				
				if(nextX >= 0 && nextY >= 0 && nextX < h && nextY < w &&
				   visited[nextX][nextY] == false && map[nextX][nextY] == 1) {
					
					Node next = new Node(nextX, nextY);
					visited[nextX][nextY] = true;
					q.offer(next);
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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];
			visited = new boolean[h][w];
			
			// 섬의 개수
			int mapCount = 0;
			
			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());
				}
			}
			
			for(int i = 0; i < h; i++) {
				for(int j = 0; j < w; j++) {
					// 방문하려는 곳이 땅이고, 아직 미방문인 경우
					if(map[i][j] == 1 && visited[i][j] == false) {
						// BFS탐색
						BFS(i, j);
						// 섬의 개수 세기
						mapCount++;
					}
				}
			}
			System.out.println(mapCount);
		}
	}
}

---

※ 생각정리 (섬의 개수)

백준 4963번 섬의 개수 문제는 단순 BFS에서 탐색을 상하좌우가 뿐만 아니라 대각방향을 포함하여 총 8개의 방향으로 이동할 수 있다.

이를 위해서 대각방향까지 이동할 수 있도록 방향성을 담은 배열 두개를 만들어주었다.

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

반복문 0~7까지 돌며 현재 좌표에서 모든 방향으로 값을 찾아가며 이동하였다.

기존 탐색문제들과 같이 이미 방문한 노드는 체크하지 않고 맵의 값이 땅인(1) 좌표만 탐색하여 정답을 찾았다.

 

-새벽코딩-