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

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

---

문제 해결

• 좌우,아래위로 탐색해야하므로 상하좌우 이동좌표를 이용하였다.

• 좌표의 값에 따라 이동할 수 있는지의 여부가 달라지므로 BFS를 이용하여 문제를 해결하였다.

• 각 단지의 속하는 집의 수를 반환해야하므로 좌표의 값이 1일 때마다 값을 추가하여 저장할 수 있는 변수를

  선언하였다.

• 이미 방문한 좌표를 다시 방문하면 추가하지 말아야 할 변수의 값이 추가되므로 이미 방문한 좌표는 재방문하지 않도록

   0으로 표시하는 것이 중요하다.

 

소스 코드

from collections import deque
n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int,input())))

# 상하좌우 이동좌표 
dx = [0,0,-1,1]
dy = [-1,1,0,0]

def bfs(x,y):
    global cnt 
    q = deque()
    q.append((x,y)) 
    cnt = 1 # 각 단지 내 집의 수를 담을 변수
    graph[x][y] = 0 # 이미 방문한 것은 재방문하지 않기 위해 0으로 표시
    while q:
        x,y = q.popleft()
        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] == 1:
                cnt += 1
                q.append((nx,ny))
                graph[nx][ny] = 0 # 이미 방문한 것은 재방문하지 않기 위해 0으로 표시
    return cnt            

answer = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1: # 그래프 순회 시 1을 만나게 되면 bfs 실행
            answer.append(bfs(i,j))              

answer.sort() # 각 단지내 집의 수를 오름차순으로 정렬
print(len(answer)) # 단지 수 출력
for i in answer: # 각 단지내 집의 수 출력
    print(i)