[ 문제 ]

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

[ 알고리즘 유형 ]

그래프 이론
그래프 탐색
너비 우선 탐색
깊이 우선 탐색

[ 정답 코드 ]

DFS

from collections import Counter
from functools import reduce

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

def dfs(i,j, cnt):
    d[i][j] = cnt
    for k in range(4):
        nx = i + dx[k]
        ny = j + dy[k]
        if 0 <= nx < n and 0 <= ny < n:
            if h[nx][ny] == 1 and d[nx][ny] == 0:
                dfs(nx, ny, cnt)

n = int(input())
h = [list(map(int, input())) for _ in range(n)] # 집
d = [[0]* n for _ in range(n)] # 단지

cnt = 0
for i in range(n):
    for j in range(n):
        if h[i][j] == 1 and d[i][j] == 0:
            cnt += 1
            dfs(i, j , cnt)

answer = reduce(lambda x, y: x+y, d)
answer = [ ans for ans in answer if ans > 0]
answer = sorted(list(Counter(answer).values()))

print(cnt)
print('\n'.join(map(str, answer)))

BFS

from collections import deque, Counter
from functools import reduce

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

def bfs(x,y,cnt):
    q = deque()
    q.append([x,y])
    d[x][y] = cnt
    while q:
        x,y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < n:
                if h[nx][ny] == 1 and d[nx][ny] == 0:
                    q.append([nx,ny])
                    d[nx][ny] = cnt

n  = int(input())
h = [ list(map(int, input())) for _ in range(n)]
d = [ [0] * n for _ in range(n)]

cnt = 0
for i in range(n):
    for j in range(n):
        if h[i][j] == 1 and d[i][j] == 0:
            cnt += 1
            bfs(i, j, cnt)

answer = reduce(lambda x,y : x+y, d)
answer = [ ans for ans in answer if ans > 0]
answer = sorted(list(Counter(answer).values()))

print(cnt)
print('\n'.join(map(str, answer)))

[ 풀이 방법 ]

기본 DFS, BFS를 적용하면 쉽게 풀리는 문제였다.
대신, 단지의 개수와 단지마다 집의 개수도 구해야됐다.

처음 풀 때는 main함수에서 변수를 초기화하고
dfs, bfs 함수에서 glbal 변수로 값을 변경해 구했다.

이번에는 다른 사람의 코드를 참고하여 다른 방식으로 구현해봤다.
d 리스트에 해당하는 단지 번호 값을 넣고
reduce로 2차원리스트를 1차원 리스트로 바꾼뒤
0보다 큰 값들만 리스트에 넣어주고
오름차순으로 출력하라했으니 오름차으로 정렬하여 출력했다.