프로그래밍 언어/파이썬
백준 2667 단지번호 붙이기 파이썬
hyun2371
2023. 5. 9. 19:14
문제
https://www.acmicpc.net/problem/2667
문제 요약
1끼리 상하좌우로 연결 → 단지
단지 수 출력하고, 각 단지 속하는 집 수 오름차순 출력
슈도 코드
1. 특정 지점 상, 하, 좌, 우 살피기
2. 주변 지점 중 값이 1이면서 방문하지 않은 지점 있으면 해당 지점 방문방문했을 때 값을 0으로 바꾸고 카운트 +1
각 단지별로 카운트 한 값을 배열에 저장한다.
방문한 지점에서 다시 상하좌우 살피며 방문 반복
3. 1, 2번의 과정을 반복하며, 방문하지 않은 지점을 방문한다.
4. 각 단지별 카운트를 오름차순으로 정렬한다.
제출코드
import sys
n = int(sys.stdin.readline())
result = []
graph = []
ind = 0
for i in range(n):
graph.append(list(map(int, sys.stdin.readline().rstrip())))
cnt = 0
def dfs(x, y):
global cnt
if x <= -1 or x >= n or y <= -1 or y >= n:
return cnt
if graph[x][y] == 1:
graph[x][y] = 0
dfs(x - 1, y)
dfs(x + 1, y)
dfs(x, y - 1)
dfs(x, y + 1)
cnt+= 1 # 단지별 집 수 저장
return cnt
return cnt
for i in range(n):
for j in range(n):
c = dfs(i,j)
if c>0:
result.append(c)
cnt =0
print(len(result))
result.sort()
print(*result, sep="\n")
배운점
전역 변수 사용: 변수 앞에 global 붙이기