[백준] 4963 : 섬의 개수 JAVA 풀이

 

 

땅인 부분에서 dfs나 bfs를 수행해서 하나의 섬을 다 탐색하고

그때마다 섬의 개수를 하나씩 증가시켜주면 되는 어렵지 않은 문제였다.

 

import java.io.*;
import java.util.*;
 
public class Main {
	
    // 상하좌우, 대각선으로 이동하기 위한 좌표
	static int[] dx = {0,0,-1,1,-1,-1,1,1};
	static int[] dy = {1,-1,0,0,1,-1,1,-1};
	
    // 지도와 해당 칸을 방문했는지 확인하기 위한 배열
	static int[][] graph;
	static boolean[][] visit;
	
    // 섬의 개수
	static int cnt = 0;
	
	static int W;
	static int H;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			
            // 0 0이 입력되면 반복문 종료
			if(W==0&&H==0) break;
			
			graph = new int[H][W];
			visit = new boolean[H][W];
			
			// 그래프 만들기
			for(int i=0;i<H;i++) {
				st = new StringTokenizer(br.readLine()," ");
				for(int j=0;j<W;j++) {
					graph[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			for(int i=0;i<H;i++) {
				for(int j=0;j<W;j++) {
                	// 1이고 아직 방문하지 않은 곳이면 dfs 수행
                    // dfs가 한 번 끝나면 하나의 섬을 탐색했다는 뜻이므로
                    // 섬의 개수를 +1
					if(graph[i][j]==1&&!visit[i][j]) {
						dfs(i,j);
						cnt++;
					}
				}
			}
			System.out.println(cnt);
			cnt=0;
		}
	}
	
	public static void dfs(int x, int y) {
		visit[x][y] = true;
		
		for(int i=0;i<8;i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx>=0&&ny>=0&&nx<H&&ny<W) {
				if(graph[nx][ny]==1&&!visit[nx][ny]) {
					dfs(nx,ny);
				}
			}
			
		}
	}
}

 

 

좀 바보같은 이야기지만 이번 문제에서 제일 어려웠던 점은..ㅋㅋㅋ

if(nx>=0&&ny>=0&&nx<H&&ny<W) {
		if(graph[nx][ny]==1&&!visit[nx][ny]) {
			dfs(nx,ny);
		}
	}

nx<H&&ny<W 이 조건을 이해하는 것이었다.

H가 세로고 W가 가로니까

nx>W&&ny<H가 되어야 할 것 같은데, 이렇게 하면 에러가 나왔다.

 

 

그래서 다시 생각해봤다.

H = 2, W = 3인 상황이다.

 

내가 생각한..일반적인 좌표상에서의 x와 y값은 이렇다.

(0,1)	(1,1)	(2,1)
(0,0)	(1,0)	(2,0)

 

하지만 이 문제에서 나는 [2x3] 크기의 2차원 배열을 사용했고

그 배열의 인덱스는 이렇다.

(0,0)	(0,1)	(0,2)
(1,0)	(1,1)	(1,2)

딱 이렇게 그려보고나니 저 조건식이 이해가 됐다.