[C/C++] 코드업(codeup) 4024번 호수의 수 구하기

▽문제 바로가기

https://codeup.kr/problem.php?id=4024

호수의 수 구하기

---

입력

첫째 줄에 두 정수 W, H가 주어진다. (단, 4 <= W, H <= 100)

지도는 직사각형으로 이루어지며, W는 지도의 너비를 의미하고, H는 지도의 높이를 의미한다. 

두 번째 줄부터 H + 1번째 줄까지 각 줄 마다 'L'또는 '.'가 W개 공백으로 구분하여 주어진다.

 

출력

출력내용은 호수의 개수를 하나의 정수로 출력한다.

 

문제 풀이

 

정말 쉬운 문제! 8방향 탐색하면서 호수이면 함수 호출해서 계속 탐색하면서 해결했습니다. 이때 자기 자신은 호수 아닌 걸로 해줘서 다시 탐색하는 일이 없도록 했습니다.

 

#include <stdio.h>

using namespace std;

char arr[101][101];
int w, h;
int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

void dfs(int row, int col){
	//범위 밖이면 리턴
	if(row==-1||col==-1||row==h||col==w) return;
	
	arr[row][col] = '.';	//자기자신은 호수아닌걸로
	
	//8방향탐색 
	for(int i=0;i<8;i++){
		if(arr[row+dy[i]][col+dx[i]]=='L') dfs(row+dy[i], col+dx[i]);
	}
	
}


int main(){
	
	scanf("%d%d", &w, &h);
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			scanf(" %c", &arr[i][j]);
		}
	}
	
	int ret = 0;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(arr[i][j]=='L'){
				dfs(i, j);
				ret++;
			}
		}
	}
	
	printf("%d", ret);
	
	return 0;
}