[C++] 백준 4963번 섬의 개수

그래프 탐색 문제.

연결 요소의 갯수를 찾아서 출력하는 문제이다.

 

 

문제 접근 방식

문제를 읽어보면 섬의 개수를 세는 것을 말한다.

섬은 그래프를 의미하며, 그래프가 총 몇 개가 만들어지는지, 즉 연결요소의 개수가 몇 개인지를 물어보는 문제이다.

 

그리고나서 DFS를 이용해서 재귀함수로 풀었다.

 

코드를 살펴보자면,

사용한 STL과 변수와 DFS메서드

w, h를 입력받고 땅과 바다를 입력받는 world배열을 만들었다.

그리고 연결요소의 갯수를 나타내는 result 변수를 만들었다.

 

dfs 메서드에서는 높이나 너비가 1보다 작거나 최대값보다 클 경우 return하도록 만들었다.

그리고 1이 아닌경우, 즉 바다인 경우(0)나 이미 방문한 경우(2) 리턴하도록 만들었다.

이 둘도 아니고 땅을 방문했을 경우 방문한 상태(2)로 만들어놓고 해당 섬에서

모든 8가지 경우를 방문하도록 재귀함수를 만들었다.

입력이 여러 케이스이므로 w와 h가 0이 되기 전까지 입력을 받는다.

그리고 연결 요소의 개수를 0으로 초기화 시킨다.

그리고 memset함수를 이용해서 world 배열의 모든 값을 0으로 초기화시킨다.

그리고 나서 섬의 정보를 입력받는다.

그리고 1인경우, dfs메서드를 호출하도록 한다.

호출했을 때 연결요소의 개수를 한 개 증가시킨다.

 

처음에 memset 메서드를 사용했는데 #include <cstring>을 하지 않아서 컴파일 에러가 났다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.