[코딩테스트 C++] 섬의 개수

오늘의 문제

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

섬의 개수

접근 방법

• 맨날 십자만 풀다가 대각선까지 있는거는 처음 접했다. 뭐 둘러볼때 사용하는 연산만 추가해주면된다.
• DFS로 그래프를 탐색한다. 주변의 8칸을 모두 탐색하여 범위 안이고, 1인 경로를 따라간다.

나의 풀이

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 50;
int n, m; // 세로, 가로
int map[MAX][MAX];
int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy[] = {0, 0, -1, 1, 1, -1, 1, -1};
// 섬의 개수

void dfs(int x, int y){
    map[y][x] = 0;
    for(int i=0;i<8;i++){
        int moveX = x + dx[i];
        int moveY = y + dy[i];
        if(moveX >= m || moveX <0 || moveY >= n || moveY <0)
            continue;
        if(map[moveY][moveX] == 1)
            dfs(moveX, moveY);
    }
}

int solution(){
    int answer = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(map[i][j] == 1){
                dfs(j, i);
                answer++;
            }
        }
    }
    return answer;
}

다른 풀이

#include <cstdio>
#include <cstring>
bool land[55][55];
bool visited[55][55];
int dc[]={1,1,0,-1,-1,-1,0,1};
int dr[]={0,1,1,1,0,-1,-1,-1};
int w,h;
void dfs(int r,int c){
	for(int i=0;i<8;++i){
		int rr=r+dr[i];
		int cc=c+dc[i];
		if(rr<=0 || rr>h || cc<=0 || cc>w) continue; 
		if(land[rr][cc]==true && visited[rr][cc]==false) {
			visited[rr][cc]=true;
			dfs(rr,cc);
		}
	}
}
int main () {
	while(scanf("%d %d",&w,&h),w!=0 || h!=0){
		for(int r=1;r<=h;++r){
			for(int c=1;c<=w;++c){
				scanf("%d",&land[r][c]);
			}
		}
		int cnt=0;
		memset(visited,0,sizeof(visited));
		for(int r=1;r<=h;++r)
			for(int c=1;c<=w;++c){
				if(land[r][c]==0 || visited[r][c]) continue;
				dfs(r,c);
				cnt++;
			}
		printf("%d\n",cnt);
	}
	return 0;
}

배울 점

• DFS를 사용해서 똑~같이 푸셨다.