[BaekJoon] 백준 4963번 _ 섬의 개수 for JAVA _ DFS 알고리즘

 

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

4963번: 섬의 개수

 

 

 

 

문제

 

 

 

---

 

DFS 알고리즘을 이용하여 풀었다.

 

 

전형적인 DFS 문제로 이해할 수 있는데

 

 

무한 루프로 돌리다가 w h 값이 0 0 이 되었을 때 멈춰야한다는 것이 추가되었다.

 

 

 

 

코드

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


public class Baek4963 {
	public static int w = 0, h = 0;
	public static int count[] = new int[2500]; // 섬의 개수
	public static int map[][] = new int[50][50];

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int index = 0;
		
		while(true) {
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			
			if(w == 0 && h == 0) break;
			
			map = new int[h][w]; // 지도 초기화
			
			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());
			}

			
			
			for(int i = 0; i < h; i++) {
				for(int j = 0; j < w; j++) {
					if(Land_dfs(i, j)) {
						count[index]++;
					}
				}
			}
			index++;		
			
		}	
			
			for(int i = 0; i < index; i++)
				System.out.println(count[i]);			
		
	}
	
	public static boolean Land_dfs(int x, int y) {
		int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
		int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
		
		if(x <= -1 || x >= h || y <= -1 || y >= w) return false;
		if(map[x][y] == 1) {
			
			map[x][y] = 0;
			
			for(int i = 0; i < 8; i++) {
				Land_dfs(x + dx[i], y + dy[i]);
			}
			
			return true;
		}
		
		return false;
		
	}
	
}

 

 

 

대각선도 확인해야 하기 때문에 dx[], dy[] 가 8개씩 나온다.

 

 

 

 

성능

 

 

 

 

 

---

 

 

남의 코드 확인

 

 

 

https://www.acmicpc.net/source/19237258

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

public class Main {

    private static final int[][] cardinalPoints = {{0, 1}, {0, -1}, {1, 0}, {1, 1}, {1, -1}, {-1, 0}, {-1, 1}, {-1, -1}};
    private static boolean[][] islands;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true) {
            StringTokenizer spec = new StringTokenizer(br.readLine());
            int width = Integer.parseInt(spec.nextToken());
            int height = Integer.parseInt(spec.nextToken());

            if(width == 0 && height == 0) {
                return;
            }

            islands = new boolean[height + 2][width + 2];

            for(int i = 1; i <= height; i++) {
                String s = br.readLine();
                for(int j = 1; j <= width; j++) {
                    islands[i][j] = s.charAt((j - 1) * 2) > '0';
                }
            }
            int result = 0;
            for(int i = 1; i <= height; i++) {
                for(int j = 1; j <= width; j++) {
                    if(islands[i][j]) {
                        result++;
                        dfs(i, j, islands);
                    }
                }
            }
            System.out.println(result);
        }
    }

    private static void dfs(int height, int width, boolean[][] islands) {
        for(int[] cardinalPoint : cardinalPoints) {
            int nextHeight = height + cardinalPoint[0];
            int nextWidth = width + cardinalPoint[1];

            if(islands[nextHeight][nextWidth]) {
                islands[nextHeight][nextWidth] = false;
                dfs(nextHeight, nextWidth, islands);
            }
        }
    }

}

 

 

 

나는 dx[], dy[]로 푼걸 cardinalPoints[][] 라는 2차원 배열을 만들어 풀었다.

 

 

dfs()가 실행되는 과정을 살펴보면

 

 

 

for(int[] cardinalPoint : cardinalPoints) {
            int nextHeight = height + cardinalPoint[0];
            int nextWidth = width + cardinalPoint[1];

            if(islands[nextHeight][nextWidth]) {
                islands[nextHeight][nextWidth] = false;
                dfs(nextHeight, nextWidth, islands);
            }
}

 

 

으로 for each문을 사용해 2차원 배열의 값을 x, y에 각각 집어넣을 수 있음을 알게되었다.

 

 

저렇게 할 수 있구나....만 알아가야 겠다.