[BOJ] 백준 2667 단지번호붙이기 (JAVA)

BFS 응용!

📑 문제

 

백준 2667번 단지번호붙이기

---

🌱 아이디어

BFS(너비우선탐색) + 구역 카운팅 문제이다! ArrayList에 구역 범위를 담으면 된다.

 

BFS 알고리즘 구현만 가능하다면 아주 쉽게 풀 수 있는 문제이다. 입력이 0, 1 단 두 개 이기 때문에 '1' 일 때만 인접해 있는 모든 '1' 을 탐색하고 범위를 카운팅해  ArrayList에 입력한다. 즉 ArrayList의 사이즈가 총 단지수이고, 저장된 요소를 오름차순으로 출력하면 된다!

 

아래 코드에 주석을 달아 놨으니 이해하는데 큰 어려움은 없을 것이다!

---

🌱 코드 및 풀이

기본적인 BFS 알고리즘이다. '1' 을 발견한다면 인접한 '1' 까지 전체 탐색하고 vi 배열을 통해 방문 처리를 해준다

 

ArrayList에 단지 수를 입력하고 ArrayList의 사이즈 = 총 단지수, ArrayList 요소 = 단지 내 집의 수가 된다.

사실 크게 어려울 건 없어서 이 정도만 알고 있어도 문제를 해결하는데 어려움은 없다고 생각합니다.

 

---

🌱 느낀 점

범위가 작아서 빠른 속도를 보여준다.

이번 문제는 BFS를 막 배우기 시작했을 때 풀어보면 큰 도움을 줄 수 있는 문제인 것 같다 ㅎㅎ

이렇게 하나의 알고리즘을 배우더라도 응용할 수 있는 문제들을 많이 풀어보면 도움이 많이 된다!