백준 2667번 단지번호 붙이기 문제풀이, 파이썬

백준 2667번 : 단지번호 붙이기 문제풀이 [파이썬] 

---

<문제>

 

2667번 문제의 내용은 아래와 같습니다. 

 

 

단지번호붙이기 성공

 

 

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력 1 복사

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력 1 복사

3
7
8
9

---

 

 

<작성한 코드>

 

---

 

 

<코드 풀이>

 

반복해서 문제를 풀다보니 이제 그래프 탐색에 대해서

어느정도 감을 잡은것같다. 

애초에 접근 자체를 이전에 풀어본 미로 문제랑

비슷하게 생각하고 접근해서 그런가 은근 쉬웠다. 

2023.02.01 - [백준 알고리즘] - 백준 2178번 : 미로 탐색 문제풀이, 파이썬

백준 2178번 : 미로 탐색 문제풀이, 파이썬

 

 

우선 본 문제는 BFS 탐색 알고리즘을 사용해 해결했다. 

 

본격적인 코드 작성 이전에 기본 세팅은 위와 같다. 

굳이 ans라는 리스트를 선언해준 이유는

나중에 답을 오름차순으로 정렬해서 출력해야하기때문에

sort 함수 쓰려고 빈 리스트를 미리 만들어주었다. 

 

 

작성한 bfs함수의 내용은 위와 같다. 

우선 상하좌우 4방향의 값을 확인해줄거니까

dx, dy 리스트를 만들어주었고, 

중복해서 카운팅하는 것을 피하기위해,

방문한 곳은 그래프에서 0으로 바꾸어 방문처리를 해주었다. 

두개의 조건문을 사용해서 주석에 단 내용대로

이동방향이 단지를 벗어나면 안되니까 continue 사용/

그래프의 값이 1일때는 역시나 방문처리를 위해 0으로 바꾸고, 카운팅해주었다.

 

위에서 애초에 bfs 함수를 작성할때 

그래프의 숫자값이 0일때는 따로 실행되는 내용을 넣지 않은 이유는 

반복문을 돌면서 값이 1인경우에만 bfs를 실행하기 위함이다. 

(애초에 그래프 안에 인접한 1이 한개도 없이 혼자서 단독으로 존재하는 1값은 없으니까)

 

 

최종적으로 값을 출력하기 위한 코드는

위의 사진과 같다.