[CodeTree/Python] 연결된 칸 찾기

문제

연결된 칸 찾기

n x n 크기의 표에서 각 칸에 0또는 1의 값이 주어져 있습니다.

1이 주어진 칸끼리 변을 공유하고 있다면 그 칸은 연결되어있다고 합니다.

연결된 가능한 많은 수의 칸들의 개수를 모두 구하여, 각 개수를 오름차순으로 출력하는 프로그램을 작성해보세요.

 

입력 형식

첫 번째 줄에는 n이 주어집니다,

두 번째 줄부터 n개의 줄에 걸쳐 n개의 0또는 1이 공백을 두고 주어집니다.

• 5 ≤ n ≤ 25

출력 형식

첫 번째 줄에는 연결된 칸들이 모인 집합의 개수를 출력합니다.

두 번째 줄 부터 여러 개의 줄에 걸쳐 오름차순으로 각 집합에 속한 칸에 개수를 출력합니다.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

해결

1로 붙어 있는 덩어리의 개수를 세고, 각 덩어리마다 칸의 개수를 카운트하는 문제

 

    다음 내용을 고려하여 코드를 작성하였다.

• 탐색 과정에서 2차원 맵을 벗어나는 경우, False를 반환
• 방문 노드의 값이 1이고 방문 처리가 되지 않은 경우: 해당 노드 카운트 및 방문 처리 후 상하좌우 방향으로 재귀 탐색, 카운트 추가
• 맵 전체 좌표에서 해당 함수를 반복(띄엄띄엄 있는 덩어리를 찾기 위함)
  
  1. 방문 노드의 값이 1이고 방문 처리가 되지 않은 경우를 시작점으로 체크하며, 덩어리 노드 개수의 카운트 1 추가
  2. 함수에서 리턴 값을 카운트로 받았으므로, 재귀 함수를 돌면서 사이즈 리스트에 카운트값 추가

n = int(input())
# 2차원 리스트 맵 생성
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

# 방문 처리를 위한 리스트 생성
    visit = []
    for i in range(n):
        visit.append([False] * n)

# 2차원 맵 내에서의 재귀함수 생성
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우, 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False

    # 현재 노드가 1이고, 해당 노드를 방문하지 않았을 시 방문 처리
    if graph[x][y] == 1 and visit[x][y] == False:
        visit[x][y] = True
        # 상하좌우 위치 모두 재귀적으로 호출하면서 노드 개수 함께 카운트
        count = 1 # 현재 노드
        count += dfs(x - 1, y)
        count += dfs(x, y - 1)
        count += dfs(x + 1, y)
        count += dfs(x, y + 1)
        return count
    return False

ans = 0
size = []

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1 and visit[i][j] == False:
            ans += 1 # 시작점 체크
            size.append(dfs(i, j)) # dfs 함수 돌면서 사이즈 리스트에 추가

print(ans)
size.sort() # 각 개수를 오름차순으로 정렬
for i in size:
    print(i)

 

오름차순으로 정렬 안 해서 한 번 틀림