#4963 : 섬의 개수

풀이방법

사용된 것:

깊이우선탐색(DFS)

 

2022.05.28

섬의 개수를 저장할 int형 변수 answer을 선언하고 0으로 초기화한다.

 

지도의 모든 칸에 대하여,

아직 방문한 적이 없는 섬 땅 부분이 발견될 때마다

answer를 1 증가시키고,

그 땅 좌표를 시작으로 dfs를 돌린다.

dfs를 돌리면서 거쳐가는 모든 땅은 방문했다고 표시해준다.

 

코드

Java(2022.05.28)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static boolean[][] map;	//지도정보
	static boolean[][] visited;	//방문여부 저장용 배열
	static int answer;	//정답 저장용 변수
	static int w, h;	//지도의 너비와 높이
	//아래는 주변 섬을 재귀탐색할 때 사용할 좌표변경용 배열
	static int[] r = {-1,-1,-1,0,0,1,1,1};
	static int[] c = {-1,0,1,-1,1,-1,0,1};

	static void dfs(int row, int col) {
		if(row<0 || col<0 || row>=h || col>=w) return;	//지도 밖이면 return
		if(visited[row][col])return;	//이미 방문한 칸이면 return
		if(!map[row][col]) return;	//바다면 return
		
		visited[row][col] = true;
		//주변 8칸에 대하여 재귀
		for(int i = 0; i<8; i++) dfs(row+r[i], col+c[i]);
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		while(true) {
			String firstLine = br.readLine();
			if(firstLine.equals("0 0")) break;	//입력값이 "0 0"이면 종료
			//필요한 값들을 읽어오고 필요한 변수들을 선언 및 초기화
			StringTokenizer st = new StringTokenizer(firstLine);
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			answer = 0;
			map = new boolean[h][w];
			visited = new boolean[h][w];
			//지도정보 읽어오기
			for(int i = 0; i<h; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j = 0; j<w; j++) if(st.nextElement().equals("1")) map[i][j] = true;
			}
			//아직 체크하지 않은 섬 땅에 대하여 깊이우선탐색
			for(int i = 0; i<h; i++) {
				for(int j = 0; j<w; j++) {
					if(map[i][j] && !visited[i][j]) {
						answer++;
						dfs(i, j);
					}
				}
			}
			//정답 문자열에 정답 값 추가
			sb.append(answer + System.lineSeparator());
		}
		//정답 출력
		System.out.print(sb);
	}

}