[白俊解答問題]2667番の小区番を貼る

8914 ワード

これは、Backjuneサイト2667に関する質問です.ちなみにPythonで問題を作りました.
https://www.acmicpc.net/problem/2667
△この文章は、以前議論した問題をコードコメントするために書かれたものです.
2667号の単番号の問題は以下の通りです.

この問題を解決するには、DFSとBFSを理解する必要があります.この2つのナビゲーション方法については、以前の投稿を参照してください.
https://velog.io/@luvlik207/%EB%B0%B1%EC%A4%80-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-1260%EB%B2%88-DFS%EC%99%80-BFS
すぐにコードコメントをしたいです.△BFSナビゲーション法を適用することで問題を解決した.
# bfs 탐색을 위한 함수
def bfs(x, y):
    global cnt	# 전역 변수
    
    # x, y가 각각 지도를 벗어나지 않는지 확인
    if 0 <= x < n and 0 <= y < n:
    	# 지도의 x, y 좌표 위치에 집이 있고, 방문한 적이 없다면
        if matrix[x][y] == 1 and visited[x][y] == 0:
            visited[x][y] = 1  # 방문한것으로 체크
            cnt += 1	# 방문한 집의 수를 더해줌
            dfs(x-1, y) # 해당 위치의 왼쪽에 집이 있는지, 방문했는지 확인(아직 방문하지 않았다면 방문하기)
            dfs(x+1, y) # 해당 위치의 오른쪽에 집이 있는지, 방문했는지 확인(아직 방문하지 않았다면 방문하기)
            dfs(x, y-1) # 해당 위치의 위쪽에 집이 있는지, 방문했는지 확인(아직 방문하지 않았다면 방문하기)
            dfs(x, y+1) # 해당 위치의 아래쪽에 집이 있는지, 방문했는지 확인(아직 방문하지 않았다면 방문하기)

n = int(input())

# matrix는 지도의 입력값을 넣을 배열, visited는 방문을 확인하기 위한 배열
matrix = [[0]*n for i in range(n)]
visited = [[0]*n for i in range(n)]

# 입력 받은 지도를 matrix에 저장
matrix = [list(map(int, input())) for i in range(n)]

# 단지 별 가구 수를 넣을 배열
village = []

for i in range(n):
    for j in range(n):
    	# 집이 있고, 아직 방문하지 않았다면
        if matrix[i][j] == 1 and visited[i][j] == 0:
            cnt = 0	# 단지별로 가구 수를 카운트
            queue = []	# 단지별로 각 가구마다 상하좌우에 이웃이 있는지 확인하기 위한 큐
            bfs(i,j)
            village.append(cnt)	# 단지별 가구 수를 추가
            
print(len(village))  # 단지 개수 출력
village.sort()	     # 단지 별 가구 수 오름차순 정렬

# 오름차순 정렬된 단지 별 가구 수 출력
for i in village:
    print(i)