[백준/Java] 4963번 : 섬의 개수

✏️ 문제 탐색

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

 

섬과 바다 지도가 주어졌을 때, 섬의 개수를 세는 문제이다.

섬이 가로 세로 대각선으로 붙어있는 경우 연결되어있는 땅으로 보고 하나의 섬으로 간주한다.

대각선도 가능하다는 것에 주의하자

✏️ 구현 아이디어 / 알고리즘

 

연결된 섬을 하나로 count하기 위해서는 인접한 곳이 섬인지 확인해야 한다.

인접 노드를 가까운 depth부터 탐색해나가는 bfs를 사용하는 것이 적절해보인다.

✏️ 시간복잡도

한 번 방문한 곳은 다시 방문하지 않으므로 시간 복잡도는 O(N) (N=노드 개수)이며,

지도의 너비w와 높이h가 각각 50 이하이므로 노드 개수는 최대 50*50=2,500개로 시간 안에 연산 가능하다.

✏️ 코드 설계

1. (0,0)에서 시작하여 인접한 곳을 방문하면서 섬인지 바다인지 확인한다.
2. 인접한 곳이 섬이면 계속해서 탐색하기 위해 큐에 넣는다. 이미 방문한 곳은 다시 방문하지 않는다.
3. 큐가 모두 비었다면  더 이상 인접한 섬이 없다는 의미. bfs 탐색이 끝날 때마다 섬이 있었다면 섬 개수를 하나 count한다.

이번 문제는 '0 0'이 입력될 때까지 테스트 케이스를 계속 받아야 한다. 따라서 main함수의 로직이 복잡해질까봐 테스트 케이스를 받는 부분을 solve()함수로 분리해서 짰다. 

 

main() : 

• while문 무한 루프
  
  • 높이 h, 너비 w를 입력받음
  • h==0 && w==0이면 while문 종료
  • 그렇지 않으면 solve() 실행

solve() : 

• 입력값 받기
  • map: int[][] 지도에 0, 1을 입력받음
• bfs 탐색
  • bfs 실행에 쓰일 큐, 방문체크, count(섬 개수)를 초기화시켜준다. 
  • map의 모든 좌표를 돌면서 bfs() 실행 (이미 방문한 좌표는 제외)
  • bfs() 리턴값이 true면 섬 개수 하나 카운트
• 모든 노드 bfs 탐색 후 count를 StringBuffer에 append

bfs() : 

• 섬이 하나라도 있으면 true값이 되는 변수 island 선언
• 시작 좌표를 큐에 넣고 방문 체크
• 큐가 빌 때까지 다음 과정 실행
  • 큐에서 좌표를 하나 꺼냄
  • 해당 좌표의 상하좌우, 대각선 인접 좌표 확인
    • 탐색 범위가 지도 밖을 벗어나면 다음 인접 좌표 탐색
    • 인접 좌표를 이미 방문했거나 값이 0(바다)이면 다음 좌표 탐색
    • 위 두 경우 모두 해당되지 않으면 섬이므로 큐에 넣고 방문 체크
    • 큐에 넣은 좌표의 값이 1이면 island=true로 변경
• island 리턴

오답 노트

• 인접 좌표를 탐색할 때 대각선을 고려하지 않아서 디버깅하는 데 시간을 날렸다.
• 너비, 높이를 이차원 배열에 반대로 대입해서 틀렸다.
• 큐에서 다음 노드를 탐색하기 위한 코드로 continue 대신 break문을 사용하는 실수를..

정답 코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int w, h;
    static int[][] map;
    static boolean[][] visited;
    static Queue<Node> q;
    static int[] dx = {0, 0, 1, -1, 1, -1, 1, -1};
    static int[] dy = {1, -1, 0, 0, 1, -1, -1, 1};
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb;

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

        while(true){
            st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            if(h==0 && w==0) break;
            else solve(h, w);
        }
        System.out.println(sb);
    }

    static void solve(int h, int w) throws IOException{
		
        //test case input
        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());
            }
        }

        q = new LinkedList<>();
        visited = new boolean[h][w];
        int count = 0;

		//BFS
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(!visited[i][j]){
                    count += bfs(i,j)?1:0; //섬이 있었다면 count+1
                }
            }
        }
        sb.append(count + "\n");
    }

    static boolean bfs(int x, int y){
        boolean island = false;

        q.offer(new Node(x, y));
        visited[x][y] = true;
        if(map[x][y]==1) island = true;

        while(!q.isEmpty()){
            Node now = q.poll();

			//인접 노드 확인
            for(int i=0; i<8; i++){
                int newX = now.x + dx[i];
                int newY = now.y + dy[i];

                //탐색 범위가 지도 밖을 벗어나면 다음 노드 탐색
                if(newX<0 || newX>=h || newY<0 || newY>=w)
                    continue;

                //인접 노드가 이미 방문했거나 바다이면 다음 노드 탐색
                if(visited[newX][newY] || map[newX][newY]==0)
                    continue;

                //인접 노드가 섬이면 큐에 add
                q.offer(new Node(newX, newY));
                visited[newX][newY] = true;
                if(map[newX][newY]==1) island = true;
            }

        }
        return island;
    }
}

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

Note

• 주로 사소한 부분에서 실수가 많은 것 같다. 다음 풀이부터는 문제를 좀 더 꼼꼼하게 봐야겠다. 
• 코드 한 줄을 짤 때도 손이 기억하는 대로 짜지 말고 머리로 생각해서 짜자...!