[白俊解答問題]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ナビゲーション法を適用することで問題を解決した.
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)
Reference
この問題について([白俊解答問題]2667番の小区番を貼る), 我々は、より多くの情報をここで見つけました https://velog.io/@luvlik207/백준-문제풀이-2667번-단지번호붙이기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol