[BOJ] 4963. 섬의개수(DFS, BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

땅이 있다면 연결된 땅을 방문하면서 방문 흔적을 남기면서 

땅의 개수를 세주면 된다.

#. BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ4963 {
 
    static int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
    static int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
 
    static public class pos {
        int x;
        int y;
 
        public pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        while (true) {
            st = new StringTokenizer(br.readLine(), " ");
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            // 0 0 이 입력되면 종료
            if (w + h == 0)
                break;
            
            int 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());
            }
            
            int res = 0;
            Queue<pos> q = new LinkedList<>();
            // 모든 좌표를 확인하면서
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    // 물이면 pass
                    if(map[i][j] == 0) continue;
                    // 땅이면 Queue에 add
                    q.add(new pos(i, j));
                    while (!q.isEmpty()) {
                        pos land = q.poll();
                        // 방문했으니까 0으로 수정
                        map[land.x][land.y] = 0;
                        // 주변을 탐색
                        for (int d = 0; d < 8; d++) {
                            int xx = land.x + dx[d];
                            int yy = land.y + dy[d];
                            // 범위 벗어나면 pass
                            if (xx < 0 || yy < 0 || xx >= h || yy >= w) continue;
                            // 물이면 pass
                            if (map[xx][yy] == 0) continue;
                            // 또 방문할 수도 있으므로 땅이면 방문했다고 미리 0으로 표시해주고
                            map[xx][yy] = 0;
                            // 방문해볼 땅을 Queue에 add
                            q.add(new pos(xx, yy));
                        }
                    }
                    res++;
                }
            }
            System.out.println(res);
        }
    }
 
}
 

#. DFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ4963_dfs {
 
    static int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
    static int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
    static int res, w, h, map[][];
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        while (true) {
            st = new StringTokenizer(br.readLine(), " ");
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            // 0 0 이 입력되면 종료
            if (w + 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());
            }
            
            res = 0;
            // 모든 좌표를 확인하면서
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    // 땅이면
                    if(map[i][j] == 1) {
                        dfs(i, j);
                        res++;
                    }                    
                }
            }
            System.out.println(res);
        }
    }
 
    public static void dfs(int x, int y) {
        // 방문했으니까 방문 처리
        map[x][y] = 0;
    
        // 주변을 탐색
        for (int d = 0; d < 8; d++) {
            int xx = x + dx[d];
            int yy = y + dy[d];
            // 범위 벗어나면 pass
            if (xx < 0 || yy < 0 || xx >= h || yy >= w) continue;
            // 물이면 pass
            if (map[xx][yy] == 0) continue;
            // 방문해볼 땅을 방문
            dfs(xx, yy);
        }
    }
}