4963. 섬의 개수

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

4963번: 섬의 개수

단순한 완전탐색 문제이다.

다만 visit을 사용하기 싫어서 탐색한 map의 값을 0으로 바꿔준 것이 특징이다.

<JAVA>

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

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

	int x, y;
}

class Main {
	static int dx[] = { 1, -1, 0, 0, -1, -1, 1, 1 };
	static int dy[] = { 0, 0, 1, -1, -1, 1, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int w, h, cnt, x, y;
		while (true) {
			cnt = 0;
			st = new StringTokenizer(br.readLine(), " ");
			h = Integer.parseInt(st.nextToken(" "));
			w = Integer.parseInt(st.nextToken(" "));
			if (w == 0 && h == 0)
				break;
			int map[][] = new int[w][h];
			for (int i = 0; i < w; ++i) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < h; ++j) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			for (int i = 0; i < w; ++i) {
				for (int j = 0; j < h; ++j) {
					{
						if (map[i][j] == 1) {
							++cnt;
							Queue<Pos> q = new LinkedList<>();
							q.add(new Pos(i, j));
							map[i][j] = 0;
							while (!q.isEmpty()) {
								Pos cur = q.poll();
								for (int dir = 0; dir < 8; ++dir) {
									int nx = cur.x + dx[dir];
									int ny = cur.y + dy[dir];
									if (nx >= w || ny >= h || nx < 0 || ny < 0 || map[nx][ny] == 0) {
										continue;
									}
									q.add(new Pos(nx, ny));
									map[nx][ny] = 0;
								}
							}
						}
					}
				}
			}
			System.out.println(cnt);
		}
	}
}

<C++>

#include<iostream>
#include<queue>
using namespace std;
struct Pos {
	int x, y;
};
int dx[] = { 1, -1, 0, 0, -1, -1, 1, 1 };
int dy[] = { 0, 0, 1, -1, -1, 1, -1, 1 };
int map[50][50];
int main()
{
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int w, h, cnt, x, y;
	Pos p;
	while (true) {
		cnt = 0;
		cin >> h >> w;
		if (w == 0 && h == 0)
			break;
		for (int i = 0; i < w; ++i) {
			for (int j = 0; j < h; ++j) {
				cin >> map[i][j];
			}
		}
		for (int i = 0; i < w; ++i) {
			for (int j = 0; j < h; ++j) {
				{
					if (map[i][j] == 1) {
						++cnt;
						queue<Pos> q;
						p.x = i;
						p.y = j;
						q.push(p);
						map[i][j] = 0;
						while (!q.empty()) {
							Pos cur = q.front();
							q.pop();
							for (int dir = 0; dir < 8; ++dir) {
								int nx = cur.x + dx[dir];
								int ny = cur.y + dy[dir];
								if (nx >= w || ny >= h || nx < 0 || ny < 0 || map[nx][ny] == 0) {
									continue;
								}
								p.x = nx;
								p.y = ny;
								q.push(p);
								map[nx][ny] = 0;
							}
						}
					}
				}
			}
		}
		cout << cnt<<"\n";
	}
}