백준 2667 단지번호붙이기 Python 3

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

2667번: 단지번호붙이기

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ2667.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
def dfs(x, y):
    global num
    num += 1
    for ddx, ddy in zip(dx, dy):
        nx = x+ddx
        ny = y+ddy
        if 0 <= nx < N and 0 <= ny < N and _map[ny][nx] == '1' and not visit[ny][nx]:
            visit[ny][nx] = 1
            dfs(nx, ny)

input = sys.stdin.readline
N = int(input())
_map = list()
for _ in range(N):
    _map.append(list(input().rstrip()))
visit = [[0]*N for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
area = 0
houses = list()
num = 0
for y in range(N):
    for x in range(N):
        if _map[y][x] == '1' and not visit[y][x]:
            num = 0
            visit[y][x] = 1
            dfs(x, y)
            houses.append(num)
            area += 1
print(area)
for num in sorted(houses):
    print(num)

---

풀이 과정

풀이 시간 9분

import sys
def dfs(x, y):
    #단지 내 집의 수 카운팅
    global num
    num += 1
    
    #인접한 4방향 탐색
    for ddx, ddy in zip(dx, dy):
        nx = x+ddx
        ny = y+ddy
        #지도 내에 위치하면서 집이 있고, 이전에 방문하지 않았다면 방문하고 탐색을 이어나간다
        if 0 <= nx < N and 0 <= ny < N and _map[ny][nx] == '1' and not visit[ny][nx]:
            visit[ny][nx] = 1
            dfs(nx, ny)

input = sys.stdin.readline
N = int(input())
_map = list()
for _ in range(N):
    _map.append(list(input().rstrip()))
    
visit = [[0]*N for _ in range(N)]
#좌 상 우 하
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

#단지 수
area = 0
#각 단지 내 집의 수
houses = list()
#단지 내 집의 수
num = 0

for y in range(N):
    for x in range(N):
    	#집이 있는데 이전에 방문하지 않았다면, 새로운 단지를 탐색한다
        if _map[y][x] == '1' and not visit[y][x]:
        	#단지 내 집의 수 초기화
            num = 0
            visit[y][x] = 1
            dfs(x, y)
            houses.append(num)
            #단지 수 카운팅
            area += 1
            
print(area)
for num in sorted(houses):
    print(num)

#시간복잡도 = O(V+E), 공간복잡도 = O(n)