[백준] 4963 - 섬의 개수 (Java)

[백준] 4963 - 섬의 개수 (Java)

문제

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

풀이/후기

일반적인 그래프탐색 문제지만, 

대각선으로 인접한 경우에도 한 가지로 판단하는 문제였다.

즉, 상하좌우 + 대각선까지 고려해야한다.

 

대각선은 현재 지점을 기준으로 {-1,-1}, {-1,1}, {1,1}, {1,-1}인 것만 생각한다면 쉽게 풀 수 있다.

dir에 상하좌우 4개와 대각선 4개까지 총 8개 경우를 넣어주면 된다.

 

예전엔 대각선 어려울 줄 알고 겁먹었었는데, 생각해보니 굉장히 간단하게 풀 수 있었다~

코드

package GraphTheory;

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

public class Problem4963 {
	
	static int w, h;
	static int[][] map;
	static boolean[][] visited;
	static int[][] dir = {{-1,0}, {1,0}, {0,1}, {0,-1}, {-1,-1}, {-1,1}, {1,1}, {1,-1}};
	static Queue<int[]> q = new LinkedList<>();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str;
		StringBuilder sb = new StringBuilder();
		
		while(true) {
			str = new StringTokenizer(br.readLine(), " ");
			
			w = Integer.parseInt(str.nextToken());
			h = Integer.parseInt(str.nextToken());
			
			if (w == 0 && h == 0) {
				break;
			}
			
			map = new int[h][w];
			for (int i=0; i<h; i++) {
				str = new StringTokenizer(br.readLine(), " ");
				for (int j=0; j<w; j++) {
					map[i][j] = Integer.parseInt(str.nextToken());
				}
			}
			
			visited = new boolean[h][w];
			int cnt = 0;
			for (int i=0; i<h; i++) {
				for (int j=0; j<w; j++) {
					if (map[i][j] == 1 && !visited[i][j]) {
						cnt++;
						bfsFn(i,j);
					}
				}
			}
			sb.append(cnt).append("\n");
		}
		
		System.out.println(sb);
	}
	
	static void bfsFn(int x, int y) {
		q.add(new int[] {x,y});
		visited[x][y] = true;
		
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int cx = cur[0];
			int cy = cur[1];
			
			for (int i=0; i<8; i++) {
				int nx = cx + dir[i][0];
				int ny = cy + dir[i][1];
				
				if (nx < 0 || nx >= h || ny < 0 || ny >= w) {
					continue;
				}
				
				if (visited[nx][ny]) {
					continue;
				}
				
				if (map[nx][ny] == 0) {
					continue;
				}
				
				q.add(new int[] {nx,ny});
				visited[nx][ny] = true;
			}
		}
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/a0eaa78bfe89d16d2f1ce480b21be4c84510f172

참고