[백준 4963] 섬의 개수 cpp-py

문제
정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다.
섬의 개수를 세어  출력해야는데 섬은 상하좌우, 대각선에 연결된 땅이 있으면 하나의 섬으로 본다.

입력
여러 개의 테스트 케이스로 이루어져 있고 0 0을 입력하면 종료된다.
각 테스트 케이스에서 첫째 줄에 지도의 너비W와 높이H가 입력된다.
(너비와 높이는 1이상 50이하)
이어서 H개의 줄에 지도가 주어지며 1은 땅 0은 바다이다.

출력
각 테스트 케이스에 대해서 섬의 개수를 출력한다.

---

접근

어떤 땅이 있는 자리에서 상하좌우, 대각선에 땅이 위치하면 하나의 섬이다.

따라서 땅을 만났을 때 더이상 이동할 수 없을 때까지 탐색을 하여 섬을 파악한다.

이 문제에서 DFS를 실행한만큼 섬의 개수가 된다.

 

구현

while문을 통해 여러 개의 테스트 케이스를 입력받으면 너비와 높이가 0이 되면 종료한다.

int count = 0;
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];
        }
   }

 

땅을 만나게 되면 DFS를 실행하고 현재 위치의 인덱스를 전달한다.

DFS가 실행한만큼 섬의 개수가 된다.

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] == 1) {
					count++;
					DFS(i, j);
				}
			}
		}

 

DFS가 실행되면 전달받은 인자에 해당되는 위치에 0을 대입한다. 이는 중복으로 방문하는 것을 막게된다.

이후 8개의 방향에 대해 탐색을 진행하여 범위 내에 있거나 땅이 있으면 재귀로 DFS를 실행한다.

void DFS(int y, int x) {
	map[y][x] = 0;

	for (int d = 0; d < 8; d++) {
		int ny = y + dir[d][0];
		int nx = x + dir[d][1];
		if (RangeCheck(ny, nx) && map[ny][nx] == 1) {
			DFS(ny, nx);
		}
	}
}

 

이후 최종적으로 섬의 개수를 출력한다.

---

전체 코드

 

c++

#include <iostream>
#include<algorithm>
#include <vector>
#include<queue>

using namespace std;

const int dir[8][2] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1} };
int w, h;
int map[50][50];

bool RangeCheck(int y, int x) {
	return(y >= 0 && y < h) && (x >= 0 && x < w);
}

void DFS(int y, int x) {
	map[y][x] = 0;

	for (int d = 0; d < 8; d++) {
		int ny = y + dir[d][0];
		int nx = x + dir[d][1];
		if (RangeCheck(ny, nx) && map[ny][nx] == 1) {
			DFS(ny, nx);
		}
	}
}
int main()
{
	while (1) {
		int count = 0;
		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 (map[i][j] == 1) {
					count++;
					DFS(i, j);
				}
			}
		}
		cout << count << endl;
	}
	
	return 0;
}

/*
상하좌우 대각선에 1이 있으면 하나의 섬
맵을 탐색하다가 1을 만나면 DFS진행 -> 현재인자를 넘겨줌
DFS 안에서는 넘겨받은 인자의 위치를 0으로
이후 상하좌우 대각선 탐색해서 1이면 재귀로 DFS
*/

 

python

import sys
from _collections import deque
def range_check(y, x):
    return (y>=0 and y<h) and (x>=0 and x<w)

def BFS(y, x):
    q = deque()
    q.append((y, x))

    dy = [1, -1, 0, 0, 1, -1, 1, -1]
    dx = [0, 0, 1, -1, 1, -1, -1, 1]
    while q:
        cy, cx = q.popleft()

        for d in range(8):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if range_check(ny, nx) and island[ny][nx] == 1:
                island[ny][nx] = 0
                q.append((ny, nx))

while True:
    w, h = map(int, input().split())
    if w==0 and h==0:
        break
    island = [list(map(int, input().split())) for _ in range(h)]

    answer = 0
    for y in range(h):
        for x in range(w):
            if island[y][x] == 1:
                answer += 1
                BFS(y, x)
    print(answer)