-
2667 단지번호붙이기알고리즘/백준 문제 2020. 5. 15. 03:14
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. �
www.acmicpc.net
- 이전에 풀었던 BFS 문제들과 비슷한데, 다른점은 출발점이 정해져 있지 않다.
- 그렇기 때문에 이중 for문을 만들어서 모든 지점을 출발점으로 하여 BFS를 실행한다.
- BFS 함수 내부에서는 초반에 방문한 좌표가 들어오면 종료시켜준다.
- 종료되지 않았다면 단지가 형성되어 있다는 의미이므로,
- while문 안에 for문을 돌때마다 단지의 아파트수 (cnt)를 증가
- 함수를 종료하기 전에 List에 cnt값을 추가한다.
- 프로그램이 종료될 시점에 List의 길이가 단지의 개수이다.
개선할 점 :
전역변수를 많이 썼다.
BFS함수 내부에 들어가기 전에 미리 방문여부를 확인하면 불필요한 호출을 막을 수 있을 듯 하다.
백준 강의에서 코드는 cnt변수가 아닌, 배열을 만들어서 각 블럭이 몇 단지에 해당되는지 표시를 해주었다.
개선을 해봐야겠다.