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

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

문제: 집들이 연결되어 있는 단지를 파악하고 총 단지의 수와 각 단지의 집이 몇개인지 파악하라. 

 

문제 이해하기!!

해당 문제는 딱 명확한 완전탐색이었습니다.

BFS, DFS든 상관은 없구요, visit 배열로 방문체크만 해준다면 바로 풀리는 문제입니다.

 

제가 푼 방식을 설명하자면,

1. 입력받은 배열을 for문으로 돌려, 아직 방문하지 않은 곳이고 집이 있는 곳이라면 DFS를 수행합니다.

2. DFS구현: DFS를 수행할 지점을 Stack에 넣고, 해당지점에서 인접한 곳의 집이면서 아직 방문하지 않은 곳을 체크합니다.

3. 체크한 곳을 Stack에 넣고 다시 Stack을 돌리며 Stack 안에 아무것도 없어질 때까지 계속 돌립니다.

4. DFS 한번 끝날때마다 단지 수 + 1이 되며 방문한 곳의 수를 저장하고 1 ~ 3번을 반복 수행 후, 정답을 출력합니다.

 

코드:

from sys import stdin
input = stdin.readline

N = int(input())
arr = [input().rstrip() for i in range(N)]
visit = [[False] * N for i in range(N)]
dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def dfs(x, y):
    S = [(x, y)]
    visit[x][y] = True
    cnt = 1
    while S:
        n, m = S.pop()
        for i in range(4):
            rn = n + dxy[i][1]
            rm = m + dxy[i][0]
            if 0 <= rm < N and 0 <= rn < N and visit[rn][rm] == False and arr[rn][rm] == '1':
                S.append((rn, rm))
                visit[rn][rm] = True
                cnt += 1
    return cnt

ans = []
for i in range(N):
    for j in range(N):
        if arr[i][j] == '1' and visit[i][j] == False:
            ans.append(dfs(i, j))
ans.sort()
print(len(ans))
for i in ans:
    print(i)