백준 4963번 :: 섬의 개수(DFS)

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

4963번: 섬의 개수

🎈 기억 할 것 (주소값 비교(==)와  값비교(equals))

 

• == 연산자는 비교하고자 하는 두개의 대상의 주소값을 비교
• equals 메소드는 비교하고자 하는 두개의 대상의 값 자체를 비교
• int, char형은 Call by Value의 형태로 기본적으로 대상에 주소값을 가지지 않는 형태로 사용.
• But String은 클래스이기에 기본적으로 Call by Reference 형태로 생성 시 주소값이 부여
• 그렇기에 String 타입을 선언했을 때 같은 값을 부여하더라도 서로간의 주소값이 다를 수가 있다.

🎈 소스 코드

 

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

public class Q4963_섬의개수 {
	static int[][] moves = {{+1, 0}, {-1, 0}, {0, +1}, {0, -1}, {+1, +1}, {-1, -1}, {-1, +1}, {+1, -1}};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n, m;
		while(true) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());

			if(n==0 && m==0) break;

			int[][] island = new int[m][n];
			for(int i=0; i<m; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<n; j++) {
					island[i][j] = Integer.parseInt(st.nextToken());
				}
			}


			int cnt = 0; // 섬의 개수
			for(int i=0; i<m; i++) {
				for(int j=0; j<n; j++) {
					// island[i][j] == "1"
					if(island[i][j]==1) {
						cnt++;
						dfs(island, i, j);
					}
				}
			}
			System.out.println(cnt);
		}
	}

	static void dfs(int[][] island, int r, int c) {
		island[r][c] = 0; // 방문한 정점
		for(int[] move : moves) {
			int nx = r+move[0];
			int ny = c+move[1];

			// 방문한 적이 없으면서 조건이 맞으면..
			if(nx >=0 && nx < island.length && ny >=0 && ny < island[0].length) {
				if(island[nx][ny]==1) {
					dfs(island, nx, ny);
				}
			}
		}


	}
}