ahttps://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
실버까지는 그래프 탐색 문제가 참 쉽다. 어째, Class 3에서 bfs, dfs 문제가 참 많이 나오는 것도 여기서 꿀빨라는것 같았다.
거두절미하고, 본 문제는 입력으로 받는 N을 통해 N*N 정사각형 내 0 또는 1의 값이 채워져있다.
여기서 1은 집이 있는 곳을 의미하며, 0은 집이 없는 곳을 의미한다.
이때, 연결된 집의 모임인 단지를 정의하면서 이 단지가 몇개가 있고, 각 단지별 집이 몇개가 있는지 알고 싶어한다.
즉, 1을 찾았을때 주변에 0이 아닌 1들이 몇개가 있는지 탐색을 해나가면서 단지마다의 집의 개수들을 탐색하면될 것이다.
코드는 다음과 같다.
dx, dy를 정의하고, bfs함수내에서는 상하좌우로 탐색을 수행하며 if내의 조건하에 참이다면 움직이고자 하는 위치의 visited를 True로 바꿔주고, deque에 움직이고자 하는 위치를 append해주었다.
그리고 cnt += 1 이 있는데, 이 의미는 단지 내의 집의 개수를 구하기 위해 cnt 변수를 추가하였다.
bfs가 한번 호출될 때, 어떤 하나의 단지내부를 탐색을 수행하게 된다.
그러면 단지 내부의 집이 몇개인지 알아야하기 때문에 cnt가 필요하다.
그렇게 bfs 함수내에서 cnt를 계속 구해나가면서 단지 내의 집의 개수를 구한 다음, return cnt를 하게 된다면 반환값은 어떤 하나의 단지 내의 집의 개수를 뜻하게 된다.
최종적으로 result의 요소들은 단지별 집의 개수들이 들어가 있을 것이다.
그래서 len(result)로 총 단지 개수를 출력하고, 정렬 후 result를 출력하라는 문제의 설명에 따라 sorted(result)의 요소들을 출력하였다.
4학년 1학기 종강이 어느덧 3주가량 앞두고 있지만, 1일 1백준은 꾸준히 해야할 것 같다.
1일 1백준 25일째...
곧 400문제 채운다!
'백준에 대가리 깨지는중' 카테고리의 다른 글
| [백준] 실버3 조합 (0) | 2023.06.05 |
|---|---|
| [백준] 실버3 구간 합 구하기 4 (0) | 2023.06.01 |
| [백준] 실버1 쿼드트리 (0) | 2023.05.30 |
| [백준] 골드4 이중 우선순위 큐 (2) | 2023.05.30 |
| [백준] 실버2 최소 힙, 최대 힙 (0) | 2023.05.29 |