무인도 여행

무인도 여행

https://school.programmers.co.kr/learn/courses/30/lessons/154540

문제

풀이(BFS)

전형적인 탐색 문제이다. 상, 하, 좌, 우로 탐색하고 범위에 벗어나거나 X이거나 방문했다면 그 뒤론 탐색하지 않는다. 그러면 하나의 무인도를 찾을 수 있다. 하지만 여러개의 무인도를 찾아야 하므로 maps 전체를 확인해봐야 한다.

1. BFS 로직
   
   BFS에서 가장 중요한 것은 더 이상 탐색하지 않아도 되는 것을 정의하는 것이다. 즉 범위에서 벗어나거나 X일 때, 방문한 곳일 때는 탐색하지 않아도 된다. 그렇지 않을 때엔 탐색을 해야하는데 total에 해당 숫자를 더해주고 방문처리를 해준다. 그리고 탐색이 끝나면 total을 리턴해준다.

2. 마지막
   
   모든 무인도를 찾기 위해선 모든 maps을 확인해봐야한다. 또한 bfs 결과가 0이면 무인도가 아니라는 소리이고 0이 아니면 무인도라는 소리이다.

결과(BFS)