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

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

 

 

<문제 분석>

1. 상하좌우대각선까지 탐색해야 한다.

2. w와 h가 0 0이면 테스트케이스를 종료한다.

 

 

<문제 풀이>

1. map에서 상하좌우대각선을 탐색한 후 1이면 방문처리한다.

2. 메인함수에서 for문을 돌려서 1을 발견하면 dfs를 돌리고 섬개수를 ++한다.

 

<주의>

1. 입력함수를 TC를 while문으로 받고 w와 h가 0이면 break 하는 식으로 구현

2. 확장할 때 새 지점이 섬인지 바다인지 체크하는 구문 빼먹음. if (A[nx][ny] == 0)

 

<코드 구현 #1>

import java.util.*;

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

public class Main {
    static int w, h;
    static int A[][];
    static boolean visited[][];

    int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
    int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
    void DFS(int x, int y) {
        visited[x][y] = true;//방문처리
        for (int i=0; i<8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;//맵 범위를 벗어나는 경우
            if (A[nx][ny] == 0) continue;//섬이 아닌 경우
            if (visited[nx][ny]) continue;// 이미 방문한 섬일 경우
            DFS(nx, ny);
        }
    }

    int count;
    void Solve() {
        count = 0;
        visited = new boolean[h][w];
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                if (visited[i][j]) continue;
                if (A[i][j] == 0) continue;
                }
                DFS(i, j);
                count++;
            }
        }
        System.out.println(count);
    }
    
	public static void main(String[] args) {
		Main m = new Main();
        Scanner in = new Scanner(System.in);
        while (true) {
            w = in.nextInt();
            h = in.nextInt();
            if (w == 0 && h == 0) break;
            A = new int[h][w];
            for (int i=0; i<h; i++) {
                for (int j=0; j<w; j++) {
                    A[i][j] = in.nextInt();
                }
            }
            m.Solve();
        }
	}
}

 

<코드 구현 #2>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

/*
1. 입력값에 TC가 여러개 주어지니 main()에서 while(true) 안에 입력값을 받도록 하자.
2. map[][]에서 1로 연결된 지역의 갯수를 찾는 문제이니 FloodFill 알고리즘을 사용하자.
3. 대각선까지 체크해야 하니 8방향으로 탐색해야 한다.
4. BFS탐색 시 Queue는 class Node(x, y)를 사용하자.
5. 가지치기 조건
  - 맵 범위 벗어나는 경우
  - 땅이 아닌 곳
  - 이미 방문한 곳
*/

public class Main {
    static int N;
    static int w, h;
    static boolean visited[][];
    static int map[][];
    static int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

    class Node {
        int x, y;
        public Node (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    void BFS(int x, int y) {
        Queue<Node> Q = new LinkedList<>();
        Q.add(new Node(x, y));
        visited[x][y] = true;
        while(!Q.isEmpty()) {
            Node now = Q.poll();
            for (int i=0; i<8; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                // 가지치기 시작
                if (nx<0 || nx>=h || ny<0 || ny>=w) continue; //범위 벗어나면 패스
                if (visited[nx][ny]) continue; //방문했으면 패스
                if (map[nx][ny] == 0) continue; //바다면 패스
                visited[nx][ny] = true; //방문체크
                Q.add(new Node(nx, ny)); //큐에 삽입
            }
        }
    }

	void Solve() {
        int count = 0;
        visited = new boolean[h][w];
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                if (map[i][j] == 0) continue;
                if (visited[i][j]) continue;
                BFS(i, j);
                count++;
            }
        }
        System.out.println(count);
	}

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        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());
                }
            }
            m.Solve();
        }
    }
}