[백준/Python] 2667번: 단지번호붙이기

문제

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

---

문제 요약

N × N 크기의 지도에서 총 단지 수와 단지 별 집의 수를 출력한다.

 

단지는 연결된 집의 모임이다.

 

여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 위아래로 다른 집이 있는 경우이다.

 

+ 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.

 

+ 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력한다.

---

코드

def dfs(x, y):
    global cnt
    check[x][y] = 1
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 <= nx < N and 0 <= ny < N and arr[nx][ny] and not check[nx][ny]:
            cnt += 1 # 단지 내 집 개수 1 증가
            dfs(nx, ny)

N = int(input())
# 지도의 가로 세로 길이

arr = [list(map(int, list(input()))) for _ in range(N)]
# 지도 입력 받기

#print(*arr)

check = [[0] * N for _ in range(N)]
# 방문 체크 배열

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

total = 0 # 총 단지 수
res = [] # 단지들의 집 개수 저장

for i in range(N):
    for j in range(N):
        if arr[i][j] and not check[i][j]:
        # 지도엔 체크되어있지만 방문하지 않은 곳이라면
            total += 1
            cnt = 1
            dfs(i, j)
            res.append(cnt)

print(total)
for num in sorted(res):
    print(num)

---

코드 설명

1. (0, 0)부터 (N-1, N-1)까지 지도에 집이 있다고 나와있지만, 아직 방문하지 않은 곳을 찾는다.

 

1 - 1. 찾았다면 총 단지 수를 1 증가시키고, cnt를 1씩 증가시키며 단지 내에 존재하는 집 개수를 dfs 함수를 통해 모두 찾는다.

+ 방문한 인덱스는 check배열에 방문 체크한다. (방문: 1, 미방문: 0)

 

2. 총 단지 수와 정렬된 단지 별 집 수를 출력한다.