[BOJ] 2667. 단지번호 붙이기

Python3

문제

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

키워드

• 그래프
• Connected Component

문제 풀이

문제 요구사항

• 정사각형 모양의 지도
  => NxN
• 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.
• 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.(대각선상에 집이 있는 경우는 연결된 것이 아니다.)
• 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램

변수 및 함수 설명

• n: 지도의 크기 (정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)
• adjMatrix : N개의 자료(0혹은 1)가 저장되는 2차원 배열
• visited : 방문했는지 확인하는 2차원 배열
• dy : 상하 이동
• dx : 좌우 이동
• apartCnt : 단지에 있는 아파트 개수
• dangji : 단지 개수
• ans : 아파트 개수 배열 (오름차순 정렬)
• ny : 다음 이동할 칸 y
• nx : 다음 이동할 칸 x

• dfs(y, x) : dfs(깊이 우선 탐색) 구현 함수

풀이

연결되어 있는 Connected Component - DFS
인접 행렬 adjMatrix

(입력 및 선언)

• 지도의 크기 n 입력받기
• adjMatrix 배열 생성
• NxN 크기의 visited 배열 생성
• dy, dx 선언

• N개의 자료 입력받고 adjMatrix에 저장하기

(dfs 함수)

• 상하좌우 총 4번 반복하기
• 다음 이동할 칸은 매개변수 y, x에 dy[i], dx[i]를 더한 값이다.
• 아래 3가지 조건 중 하나를 만족하면 건너뛴다.
  1) ny나 nx가 0보다 작을 때, ny나 nx가 n보다 크거나 같을 때
  2) 갈 수 없는 곳, 즉 0일 때
  3) 이미 방문한 곳일 때
• 그렇지 않으면, visited[ny][nx]에 1을 넣고, 아파트 개수를 하나 늘린다.
• dfs 함수를 다시 호출한다. 이때 인자는 ny와 nx이다.

(단지 찾기)

• NxN 만큼 반복하기
• 만약 단지가 없으면 지나간다
• 만약 이미 방문했던 곳이라면 지나간다
• 단지도 있고, 방문하지 않은 곳이면 새 단지가 시작하는 곳이므로 danji를 1 늘리고, 해당 칸의 visited를 True로 바꾼다.
• dfs 함수를 호출한다
• dfs 함수에서 계산된 단지 내 아파트 총 개수를 ans 배열에 넣고, 아파트 총 개수 변수(apartCnt)는 0으로 초기화한다.
  => 다음 단지가 나오면 1부터 시작해야 하기 때문

(최종 출력)

• ans 배열을 오름차순으로 정렬한다
• 단지 개수를 출력한다
• ans 배열에 있는 원소를 출력한다

최종 코드

n = int(input())

adjMatrix = []
visited = [[0 for _ in range(n)] for _ in range(n)]

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

apartCnt = 0
danji = 0
ans = []

for i in range(n) :
    adjMatrix.append(list(map(int, input())))
    
# dfs(num) - Recursion
def dfs(y, x) :
    global apartCnt
    for i in range(4) :
        ny = y + dy[i]
        nx = x + dx[i]
        if ny < 0 or nx < 0 or ny >= n or nx >= n :
            continue
        if adjMatrix[ny][nx] == 0 :
            continue
        if visited[ny][nx] != 0 :
            continue
        visited[ny][nx] = 1
        apartCnt += 1
        dfs(ny, nx)
        
for i in range(n) :
    for j in range(n) :
        if adjMatrix[i][j] == 0 : continue
        if visited[i][j] != 0 : continue
        danji += 1
        apartCnt += 1
        visited[i][j] = True
        dfs(i, j)
        ans.append(apartCnt)
        apartCnt = 0
        
ans.sort()
print(danji)
for i in ans :
    print(i)

(+ 2023/10/11 add)

• bfs 풀이

from collections import deque

n = int(input())

adjMatrix = []
visited = [[0 for _ in range(n)] for _ in range(n)]

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

bfsQueue = deque([])

cnt = 0
ans = []

for i in range(n) :
    adjMatrix.append(list(map(int, input())))

def bfs():
    apartCnt = 1
    while bfsQueue:
        curY, curX = bfsQueue.popleft()
        for i in range(4):
            ny = curY + dy[i]
            nx = curX + dx[i]
            if 0 <= ny < n and 0 <= nx < n:
                if adjMatrix[ny][nx] == 1 and visited[ny][nx] == 0:
                    visited[ny][nx] = 1
                    bfsQueue.append([ny, nx])
                    apartCnt += 1
    ans.append(apartCnt)

for i in range(n):
    for j in range(n):
        if adjMatrix[i][j] == 1 and visited[i][j] == 0:
            bfsQueue.append([i, j])
            visited[i][j] = 1
            bfs()
            cnt += 1

ans.sort()

print(cnt)
for i in ans:
    print(i)