[99클럽 코테 스터 TIL 8일차 / 백준 2667] 단지 번호 붙이기 (Python)

 

일단 문제를 보면 넓이를 구하는 것이기 때문에 BFS 방법을 사용해야 한다는 것을 알 수 있다.

 

내 코드

from collections import deque
# 방향
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]

# 지도 크기 입력받기
n = int(input())

Map = []
num = []

# 지도 상태 입력받기
for i in range(n):
    Map.append(list(map(int, list(input()))))

queue = deque([])

def bfs() :
    cnt = 0               # 단지 수
    for i in range(n):
        for j in range(n):
            house_num = 0 # 단지에 속하는 집 수
            if Map[i][j] == 1:
                cnt += 1
                queue.append([i,j])
                while queue:
                    # 첫 위치 큐에 삽입
                    x, y = queue.popleft()
                    for dx, dy in dir:
                        nx, ny = x + dx, y + dy
                        # 범위를 벗어나지 않고 이동 가능한 경우 해당 위치 큐에 삽입
                        if 0 <= nx < n and 0 <= ny < n and Map[nx][ny] == 1:
                            Map[nx][ny] = -1
                            queue.append([nx, ny])
                            house_num += 1
                if house_num == 0:
                    house_num = 1
                num.append(house_num)

    print(cnt)
    num.sort()
    for i in num:
        print(i)
bfs()

 

이어져 총 단지 수와 단지내 수 모두 구해야하기 때문에 지도를 돌며 방문한적이 없고 1인 경우 이어져 있는 집 개수를 구하도록 하였고 이때 단지수는 +1이 된다. 그리고 while문내에서 이어진 집이 무엇인지 구하는데 이때 이어진 집을 구할때마다 해당 단지의 집 개수는 +1이된다.

 

1. for문을 통해 모든 위치를 조사하는데 해당위치의 집을 방문해본적 없고 값이 1인 경우, 이어진 집이 있는지 조사

2. 이때 단지 수 +1

3. while문을 이용해 queue가 없을때까지 반복

4. 해당 집의 좌, 우, 상, 하를 조사하여 방문한적 없고 값이 1인 경우 queue에 해당 집 넣고 방문한 것을 표시하기 위해 Map[nx][ny] 에 값 -1을 넣어준다

5. 집 수 +1

6. while 반복문이 끝나면 해당 단지의 집 개수를 num리스트에 넣어준다

7. 단지 내 집 개수인 num 리스트를 sort함수를 이용해 오름차순으로 정렬해준다

 

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