[Python] 백준 2667번 : 단지번호붙이기

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

 

---

 

 

 

• 대각선상에 집이 있는 경우는 연결된 것이 아니다 == 상하좌우 확인

 

DFS

import sys

N = int(sys.stdin.readline().rstrip())
graph = [ list(map(int,sys.stdin.readline().rstrip())) for _ in range(N)]
result = []
cnt = 0

def dfs(x, y):
    global cnt
    
    if x < 0 or x >= N or y < 0 or y >= N:
        return False
    
    if graph[x][y] == 1:
        cnt += 1
        graph[x][y] = 0
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)
        
        return True
    
    return False

for i in range(N):
    for j in range(N):
        if dfs(i,j):
            result.append(cnt)
            cnt2 = 0

result.sort()

print(len(result))
for i in result:
    print(i)

• https://dojang.io/mod/page/view.php?id=2364

파이썬 코딩 도장: 33.1 변수의 사용 범위 알아보기

• 변수 사용 범위 이해하기. global, nonlocal

 

BFS

import sys
from collections import deque

N = int(sys.stdin.readline().rstrip())

graph = []
result = []
cnt = 0

for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))


dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs(x, y):
    
    global cnt
    queue = deque()  # 큐 선언
    queue.append([x, y])
    cnt += 1
    
    while queue:
        x, y = queue.popleft()
        graph[x][y] = 0
        
        for i in range(4):
            
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            
            if graph[nx][ny] == 0:
                continue

            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append([nx, ny])
                cnt += 1


for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            bfs(i, j)
            result.append(cnt)
            cnt = 0

result.sort()

print(len(result))
for i in result:
    print(i)