[알고리즘 일기 - 파이썬] 170. 단지번호붙이기

문제 170. (2022-01-31)

 

2667번: 단지번호붙이기

Baekjoon 2667. 단지번호붙이기

[파이썬(python) 풀이]

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

 

---

 

입력

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

 

---

출력

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

 

---

 

입력 예시

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

 

---

 

출력 예시

3
7
8
9

 

---

❧ 정답

 

 

🔎IDEA) dfs - 이전에 방문 집들의 개수를 dfs를 재귀 호출하며 누적하여 더한다.

• cities : 그래프 정보를 담은 리스트
• visited : 방문 처리 및 거리 계산을 위한 리스트
• flag : 예외처리를 위한 변수(k와 일치하는 거리가 없을 경우)

 

[Line 20]
👉 지도를 탐색하며 집이 있을 경우, dfs를 재귀 호출하여 연결된 집들을 모두 탐색해간다.
👉 이때, 다음에 방문한 노드에서 이후에 방문한 집들에 대한 개수를 모두 리턴하여 cnt에 누적하여 더한다.
👉 최종적으로는 하나로 연결된 집들에 대해 그 개수를 리턴하게 한다.

 

[Line 30]
👉 단지의 첫 시작 점에 대해 dfs를 수행하여 연결된 집들의 개수를 구해, house에 추가한다.

 

[Line 32]
👉 각 집들의 개수를 오름차순으로 출력해야하므로 sorted()메서드로 정렬을 수행하고, 리스트의 원소를 개행으로 구분하여 출력한다.
💡 [ "명령문" for i in range(n)] 의 표현식은 for문을 한 줄로 표현하기 위한 방법으로 짧은 반복문의 경우 간결하게 표현할 수 있도록 돕는다!