[인프런] 단지 번호 붙이기

---

문제설명

그림1과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌,우 혹은 아래,위로 다른 집이 있는 경우를 말한다. 대각선 상에 집이 있는 경우는 연결된 것이 아니다. 그림 2는 그림1을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성해라.

 

입력조건

• 첫 줄에는 지도의 크기 N(5 <= N <= 25)이 입력되고 그 다음 N줄에는 각각 N개의 자료(0 혹은 1)가 입력된다.

출력조건

• 첫 줄에는 총 단지수를 출력해라

사고과정

• DFS, BFS 모두를 사용해서 풀 수 있는 문제였다. 그래서 2가지 방법 모두 도전했다. DFS를 사용해 풀이할 때 단지 수마다 카운트를 하는 기능을 구현하는 데 좀 우회해서 구현했다.. 코드가 장황해졌다. 사실 DFS를 풀 때, 예전에 풀어본 음료수 얼려먹기 문제에서 사용한 풀이스킬을 적용했는데, 오히려 이것이 장황한 코드가 되는 주 이유가 된 것 같다. 강의 풀이랑 비교해보니 매우 장황한 코드임을 깨달았다. 내가 구현했을 때는 단지 수 카운트를 DFS 모두 탐색 한 후 맵을 돌면서 카운트했는데, 강의에서는 DFS 탐색하면서 동시에 카운트했다.. 배울 점이 많다..
• BFS 풀이는 그래도 강의에서 구현한 것과 매우 비슷하게 잘 구현했다. BFS가 좀 더 나은 것 같기도 하고.. 여튼 2가지 방법 모두 계속 연습해야겠다.

풀이

- DFS 풀이(강의 풀이)

n = int(input())
board = [list(map(int, input())) for _ in range(n)]
res = []

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


def DFS(x, y):
    global cnt
    cnt += 1
    board[x][y] = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and board[nx][ny] != 0:
            DFS(nx, ny)


for i in range(n):
    for j in range(n):
        if board[i][j] == 1:
            cnt = 0
            DFS(i, j)
            res.append(cnt)
res.sort()
print(len(res))
for r in res:
    print(r)

- BFS 풀이

from collections import deque

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

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

def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = 1
    member = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 1 and visited[nx][ny] == 0:
                board[nx][ny] = 0
                visited[nx][ny] = 1
                member += 1
                queue.append((nx, ny))
    return member


cnt = 0
result = []
for i in range(n):
    for j in range(n):
        if board[i][j] == 1: # 집일 경우
            member = bfs(i, j)
            result.append(member)
            cnt += 1
print('cnt:', cnt)
result.sort()
for res in result:
    print(res)
print()