[백준/Python] 4963번: 섬의 개수

4963번: 섬의 개수 (acmicpc.net)

4963번: 섬의 개수

---

문제 해석

지도가 주어지면 총 섬의 개수를 출력하는 문제이다.

지도에서 서로 인접한 가로, 세로, 대각선의 Land들을 하나의 섬이라고 한다.

---

코드

---

문제 풀이

bfs를 이용하여 문제를 풀었다.

처음 v는 인접한 땅을 체크하기 위해 방향벡터를 list로 만들어주었다.

각 테스트케이스마다 while문을 돌면서 반복하며,
w, h에 너비와 높이를 저장하고 만약 둘다 0이 입력됐다면 break하여 코드를 종료한다.

arr는 지도의 값을 입력받았고 bfs를 사용하기 위해 que와 check를 선언해 주었다.
count는 섬의 개수를 센다.

그리고 전체 지도를 완전탐색하게 되는데 만약 Land가 나오면 그 부분부터 bfs를 돌며 인접한 Land들을 모두 check하게 된다. bfs를 돈 Land들은 하나의 섬이라고 볼 수 있다.
그 후, 탐색 중 Land지만 이미 bfs를 돌아 check가 된 것들은 그냥 넘어간다.
이런 방식으로 완전탐색하며 섬들을 count한다.

따라서 이중 for문 안을 보면 if문으로 Land이고 check가 안된 곳을 찾으며 있을 경우 count에 1 더해주고 bfs를 돌게 된다.

여기서 인접리스트를 사용하지 않았기 때문에 24번째 줄을 보면 방향벡터를 더해 일일이 대입하여 인접한 Land를 찾았다.
IndexError는 예외처리를 통해 continue하게 하였고 또한 파이썬은 list[-1]이 끝자리 원소이므로 22번째 줄 if문을 통해 continue시켰다.