반응형
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수
www.acmicpc.net
bfs 문제.
입력받은 데이터를 순서대로 읽어들이면서, 1을 만날 경우 해당 위치에서 bfs로 도달할 수 있는 모든 지점을 확인한다.
bfs로 탐색하면서 count를 증가시키고, bfs 탐색이 끝난 뒤 count값을 저장하는 식으로 문제를 해결할 수 있다.
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 프로그래머스. 스티커 모으기(2) (Level 4) (0) | 2020.01.18 |
|---|---|
| [Python] 프로그래머스. 땅따먹기 (Level 2) (0) | 2020.01.16 |
| [Python] 백준 5397. 키로거 (0) | 2020.01.13 |
| [Python] 프로그래머스. 입국 심사 (Level 3) (0) | 2020.01.11 |
| [Python] 백준 9012. 괄호 (0) | 2020.01.10 |