4963_섬의 개수 (JAVA) (C++)

4963번: 섬의 개수

 

[C++] - ① BFS

#include <iostream>
#include <cstring> //memset
#include <queue>
using namespace std;

int w=1;
int h=1;
int map[51][51] = {0,};
bool visited[51][51] = {false};
int ans = 0;

struct XY{
    int x; int y;
};
int dx[] = {-1,-1,-1,0,0,1,1,1};
int dy[] = {-1,0,1,-1,1,-1,0,1};

void bfs(XY xy){
    queue<XY> q;
    q.push(xy);
    
    while(!q.empty()){
        XY cur = {q.front().x, q.front().y};
        q.pop();

        for(int i=0; i<8; i++){
            XY next = {cur.x+dx[i], cur.y+dy[i]};

            if(next.x>=0&&next.x<h && next.y>=0&&next.y<w){
                if(!visited[next.x][next.y] && map[next.x][next.y]==1){
                    visited[next.x][next.y] = true;
                    q.push(next);
                }
            }
        }
    }
}

int main(){
    while(true){
        cin >> w >> h;
        if(w==0 && h==0)
            break;

        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                cin >> map[i][j];
            }
        }

        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(!visited[i][j] && map[i][j]==1){
                    visited[i][j] = true;
                    bfs({i,j});
                    ans++;
                }
            }
        }

        cout << ans << endl;

        w=0; h=0; ans = 0;
        memset(visited, false, sizeof(visited));
        memset(map, 0, sizeof(map));
    }

    return 0;
}

 

 

 

[C++] - ② DFS

#include <iostream>
#include <cstring> //memset
using namespace std;

int w=1;
int h=1;
int map[51][51] = {0,};
bool visited[51][51] = {false};
int ans = 0;

struct XY{
    int x; int y;
};
int dx[] = {-1,-1,-1,0,0,1,1,1};
int dy[] = {-1,0,1,-1,1,-1,0,1};

void dfs(XY cur){
    for(int i=0; i<8; i++){
        XY next = {cur.x+dx[i], cur.y+dy[i]};

        if(next.x>=0&&next.x<h && next.y>=0&&next.y<w){
            if(!visited[next.x][next.y] && map[next.x][next.y]==1){
                visited[next.x][next.y] = true;
                dfs(next);
            }
        }
    }
}

int main(){
    while(true){
        cin >> w >> h;
        if(w==0 && h==0)
            break;

        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                cin >> map[i][j];
            }
        }

        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(!visited[i][j] && map[i][j]==1){
                    visited[i][j] = true;
                    dfs({i,j});
                    ans++;
                }
            }
        }

        cout << ans << endl;

        w=0; h=0; ans = 0;
        memset(visited, false, sizeof(visited));
        memset(map, 0, sizeof(map));
    }

    return 0;
}

 

 

 

[JAVA] - BFS

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int ans = 0;
	static int[] dx = {-1,0,1,-1,1,-1,0,1};
	static int[] dy = {1,1,1,0,0,-1,-1,-1};
	static class XY{
		int x; int y;
		public XY(int x, int y){
			this.x = x; this.y= y;
		}
	}

	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		int w=1; int h=1;
		while(true){
			w = sc.nextInt();
			h = sc.nextInt();
			if(w==0 && h==0)
				return;

			ans = 0;
			int[][] map = new int[h][w];
			boolean[][] visited = new boolean[h][w];
			for(int i=0; i<h; i++){
				for(int j=0; j<w; j++){
					map[i][j] = sc.nextInt();
				}
			}

			for(int i=0; i<h; i++){
				for(int j=0; j<w; j++){
					if(map[i][j]==1 && !visited[i][j]){
						land(map, visited, i, j);
						ans++;
					}
				}
			}
			System.out.println(ans);
		}
	}

	private static void land(int[][] map, boolean[][] visited, int a, int b){
		Queue<XY> q = new LinkedList<>();
		q.offer(new XY(a,b));
		visited[a][b] = true;

		while(!q.isEmpty()){
			int x = q.peek().x;
			int y = q.peek().y;
			q.poll();

			for(int i=0; i<8; i++){
				int xx = x + dx[i];
				int yy = y + dy[i];

				if(xx>=0&&xx<map.length && yy>=0&&yy<map[0].length){
					if(map[xx][yy]==1 && !visited[xx][yy])
						land(map, visited, xx, yy);
				}
			}
		}
	}
}

 

1. 간단한 BFS문제이다. 1로 연결된 개수만 구하면 끝!

 

 

2. 상하좌우 + 대각선 - 위의 그림처럼 dx[], dy[]를 초기화한다.