10. 섬의 크기(중)
View as PDF
정사각형으로 이루어져 있는 섬과 바다의 지도가 주어진다.
어떤 칸과 가로, 세로 또는 대각선으로 인접한 8개의 칸은 이어져있는 섬으로 본다.
가장 큰 섬의 크기를 출력하는 프로그램을 작성하시오.
1칸의 크기는 1이고, 모든 칸의 크기는 같다.
입력
- 첫 번째 줄에 지도의 높이 \(h\)와 너비 \(w\)의 값이 주어진다.\((1 ≤ h, w ≤ 50)\)
- 둘째 줄부터 \(h\)개의 줄에 지도가 주어진다. \(1\)은 섬, \(0\)은 바다이다.
출력
- 가장 큰 섬의 크기를 출력한다.
입력 예시 1
4 5
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
출력 예시 1
4
힌트
- 지도를 그래프로 나타내면, 칸 하나가 노드이고 8방향의 간선이 존재한다고 생각할 수 있다.
Comments
이 문제도 트리 탐색으로 생각됩니다. 마찬가지 BFS, DFS 어떤 것을 사용해야 할까요? 여러분들의 토론을 아래에 기다립니다.