[BOJ/JAVA] 백준 4963 : 섬의 개수 (자바)

문제 정보

  문제명   - 섬의 개수
  난이도   - 실버 II
문제 번호 - 4963번

---

문제 링크

BOJ_S2_4963_섬의_개수_BFS

4963번: 섬의 개수

---

문제

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

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

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

---

입력

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

---

출력

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

---

예제 입력/출력

예제 입력	예제 출력
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	0 1 1 3 1 9

---

알고리즘 분류

● 그래프 이론
● 그래프 탐색
● 너비 우선 탐색
● 깊이 우선 탐색

---

소스코드 - BFS

package Lv2_Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
/**
 * @author HanHoon
 * @category 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
 * https://www.acmicpc.net/problem/4963
 */
class Pair{
	int y;
	int x;
	public Pair(int y, int x) {
		this.y = y;
		this.x = x;
	}
}
public class BOJ_S2_4963_섬의_개수_BFS {
	static int W, H, map[][];
	static boolean[][] isVisited;
	// 좌상, 좌, 좌하, 하, 우하, 우, 우상, 상
	static int[] dRow = {-1, 0, 1, 1, 1, 0,-1,-1};
	static int[] dCol = {-1,-1,-1, 0, 1, 1, 1, 0};
	
	static void bfs(Pair start) {
		Queue<Pair> queue = new LinkedList<>();
		queue.add(start);
		while(!queue.isEmpty()) {
			Pair pair = queue.poll();
//			isVisited[pair.y][pair.x] = true;	// 여기서 해주면 메모리 초과 발생
			// 8방 탐색
			for (int i = 0; i < 8; i++) {
				// 좌상, 좌, 좌하, 하, 우하, 우, 우상, 상
				int next_Row = pair.y + dRow[i];
				int next_Col = pair.x + dCol[i];
				// 범위내에 있다면
				if(next_Row < 0 || next_Row >= H || next_Col < 0 || next_Col >= W)
					continue;
				// 인접한 섬들이 없거나 || 방문했을 때
				if(map[next_Row][next_Col] == 0 || isVisited[next_Row][next_Col])
					continue;
				queue.add(new Pair(next_Row, next_Col));
				// 여키서 체크해줘야 중복 방지로 메모리 초과 x
				isVisited[pair.y][pair.x] = true;
				isVisited[next_Row][next_Col] = true;
			}
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder str = new StringBuilder();
		StringTokenizer st = null;

		while(true) {
			// 첫줄은 W, H값을 받아옴
			st = new StringTokenizer(br.readLine(), " ");
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			// 끝값이 0 0이면  while문 정지
			if(W == 0 && H ==0) break;
			// WxH 크기의 map 생성, visited 생성
			map = new int[H][W];
			isVisited = new boolean[H][W];
			int count = 0;
			
			// map의 값을 받아옴
			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());
				}
			}
			// 방문하지 않은 && 섬인경우 bfs 실행 후 cnt++
			for (int i = 0; i < H; i++) {
				for (int j = 0; j < W; j++) {
					if(!isVisited[i][j] && map[i][j] == 1) {
						bfs(new Pair(i, j));
						count++;
					}
				}
			}
			// 섬의 개수 cnt 출력
			str.append(count).append("\n");
		}
		System.out.print(str);
		br.close();
	}
}

소스코드 - DFS

package Lv2_Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * @author HanHoon
 * @category 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
 * https://www.acmicpc.net/problem/4963
 */
public class BOJ_S2_4963_섬의_개수_DFS {
	static int W, H, map[][];
	static boolean[][] visited;
	// 좌상, 좌, 좌하, 하, 우하, 우, 우상, 상
	static int[] d_col = {-1,-1,-1, 0, 1, 1, 1, 0};
	static int[] d_row = {-1, 0, 1, 1, 1, 0,-1,-1};
	
	// row 행(가로), col 열(세로)
	private static void dfs(int row, int col) {
		// 방문했다고 표시
		visited[row][col] = true;
		
		// 8방 탐색
		for (int i = 0; i < 8; i++) {
			// 좌상, 좌, 좌하, 하, 우하, 우, 우상, 상
			int next_row = row + d_row[i];
			int next_col = col + d_col[i];
			// 범위내에 있다면
			if(next_row < 0 || next_row >= H || next_col < 0 || next_col >= W)
				continue;
			// 인접한 섬들이 있고 && 방문하지 않았을때
			if(map[next_row][next_col] == 1 && !visited[next_row][next_col])
				// 탐색 실시
				dfs(next_row, next_col);
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder str = new StringBuilder();
		StringTokenizer st = null;

		while(true) {
			// 첫줄은 W, H값을 받아옴
			st = new StringTokenizer(br.readLine(), " ");
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			// 끝값이 0 0이면  while문 정지
			if(W==0&&H==0) break;
			// WxH 크기의 map 생성, visited 생성
			map = new int[H][W];
			visited = new boolean[H][W];
			int cnt = 0;
			
			// map의 값을 받아옴
			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());
				}
			}
			// 방문하지 않은 && 섬인경우 dfs 실행 후 cnt++
			for (int i = 0; i < H; i++) {
				for (int j = 0; j < W; j++) {
					if(!visited[i][j] && map[i][j] == 1) {
						dfs(i,j);
						cnt++;
					}
				}
			}
			// 섬의 개수 cnt 출력
			str.append(cnt).append("\n");
		}
		System.out.println(str);
		br.close();
	}
}

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---