문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

---

Python

from sys import stdin
from collections import deque

direction=[(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]
answer=[]

def bfs(graph, start, w, h):
    q=deque()
    q.append(start)

    while q:
        current=q.popleft()
        for i in direction:
            x=current[0]+i[0]
            y=current[1]+i[1]
            if 0<=x<w and 0<=y<h and graph[x][y]:
                q.append((x, y))
                graph[x][y]=0
    return 1

while 1:
    t = list(map(int, stdin.readline().strip().split()))
    if not sum(t): break

    graph=[list(map(int, stdin.readline().strip().split())) for _ in range(t[1])]
    result=0
    for i in range(t[1]):
        for j in range(t[0]):
            if graph[i][j]:
                result+=bfs(graph, (i,j), t[1], t[0])

    answer.append(result)

for i in answer:
    print(i)

Java

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

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        LinkedList<int[]> directions=new LinkedList<>();
        for(int i=-1; i<2; i++)
            for(int j=-1; j<2; j++)
                if(i!=0 || j!=0)
                    directions.add(new int[]{i, j});

        while(true){
            String s=br.readLine();
            StringTokenizer st=new StringTokenizer(s);
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            if(w==0 && h==0)
                break;

            int[][] graph=new int[h][w];
            for(int i=0; i<h; i++) {
                s = br.readLine();
                st = new StringTokenizer(s);
                for (int j = 0; j < w; j++)
                    graph[i][j] = Integer.parseInt(st.nextToken());
            }

            int result=0;
            for(int i=0; i<h; i++)
                for(int j=0; j<w; j++){
                    if(graph[i][j]==1){
                        Queue<int[]> q=new LinkedList<>();
                        q.add(new int[]{i, j});

                        while(!q.isEmpty()){
                            int[] current=q.poll();
                            for(int[] k:directions){
                                int x=current[0]+k[0];
                                if(x<0 || x>=h)
                                    continue;
                                int y=current[1]+k[1];
                                if(y<0 || y>=w)
                                    continue;

                                if(graph[x][y]==1){
                                    graph[x][y]=0;
                                    q.add(new int[]{x, y});
                                }
                            }
                        }
                        result++;
                    }
                }
            bw.write(result+"\n");
        }
        bw.flush();
    }
}

---

해결 과정

1. 모든 노드를 탐색해야 하므로 BFS가 빠르다고 판단했다. Graph의 모든 요소를 탐색하면서 1을 발견하면 Queue에 넣고 BFS를 돌렸다.
2. Visited 배열을 만들 필요 없이 Graph에서 값이 1인 노드에 대해서 탐색하고 1->0 으로 바꿔줬다.

3. 😁