2667번 단지번호붙이기(BFS, 연결요소) - ☆

#문제링크 : https://www.acmicpc.net/problem/2667

 

전략 : BFS를 이용하여 방문하지 않았고 행렬의 값이 1인 노드를 방문한다. 해당 노드로부터 상,하,좌,우에 위치한 노드들이 값이 1이고 방문하지 않은 노드이면서 행렬인덱스를 초과하지 않으면 큐에 추가한다. 큐에 추가할때마다 숫자를 세어주고, check할때에는 단지번호(village)를 부여한다.

※주의사항

1. BFS의 작동원리를 잘 생각하고 이해한다.

2. 노드의 움직임의 범위가 상, 하, 좌, 우로 정해져 있으므로 인접리스트로 구현할 필요가 없다.

Code