[Algorithm] 단지 번호 붙이기 (DFS, BFS) (Feat. 이차원 배열 입력 받기)

0110100
0110101
1110101
0000111
0100000
0111110
0111000

입력값이 위처럼 공백 없이 들어올 때,

[[0, 1, 1, 0, 1, 0, 0], 
[0, 1, 1, 0, 1, 0, 1], 
[1, 1, 1, 0, 1, 0, 1], 
[0, 0, 0, 0, 1, 1, 1], 
[0, 1, 0, 0, 0, 0, 0], 
[0, 1, 1, 1, 1, 1, 0], 
[0, 1, 1, 1, 0, 0, 0]]

이렇게 출력하고 싶었는데

[[110100], 
[110101], 
[1110101], 
[111], 
[100000], 
[111110], 
[111000]]

이러한 형태로 나와서 에러가 떴다.

for _ in range(n):
    graph.append(list(map(int, input().split())))

위처럼 코드를 짰었는데, split()은 문자열을 일정한 규칙으로 잘라서 리스트로 만들어주는 함수 이다. 나는 int형의 입력값을 나누려고 하므로 split()을 없애고 다시 출력했더니 정상적으로 나왔다.

for _ in range(n):
    graph.append(list(map(int, input())))

💡 문자열!!! 을 나눌 때 split() 사용!
💡 붙어있을 때 (띄어쓰기 없을 때) split() 사용 X

---

BFS 풀이

1. n * n 돌면서 1인 부분 찾아 bfs 호출
2. 넓이 우선 탐색이므로 deque 사용하여 append, popleft 사용하면서 상하좌우 돌면 된다!

from collections import deque


def bfs(i, j, a):
    global cnt
    q = deque()
    q.append((i, j))
    visited[i][j] = 1
    cnt += 1

    while q:
        x, y = q.popleft()
        for i in range(4):
            xx = x + dx[i]
            yy = y + dy[i]
            if (0 <= xx < n) and (0 <= yy < n):
                if (visited[xx][yy] == 0) and (graph[xx][yy] == 1):
                    graph[xx][yy] = a
                    q.append((xx, yy))
                    cnt += 1


n = int(input())
graph = []
#graph = [list(map(int, input())) for _ in range(n)]
for _ in range(n):
    graph.append(list(map(int, input())))

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

cnt = 0
a = 2
answer = []
visited = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            bfs(i, j, a)
            a += 1
            answer.append(cnt)
            cnt = 0

print(len(answer))
answer.sort()
for x in answer:
    print(x)

띄어쓰기 없는 배열 입력 받는 부분이 조금 막혔을 뿐 bfs 자체는 문제 없이 구현 완료!

DFS 풀이

1. 마찬가지로 n * n 돌면서 dfs 호출하기
2. 깊이 우선 탐색이므로 한 노드(현재 좌표)에서 간선이 4개 뻗어야 한다! (상하좌우로)

def dfs(i, j):
    global cnt

    graph[i][j] = 0

    for a in range(4):
        xx = i + dx[a]
        yy = j + dy[a]
        if (0<=xx<n) and (0<=yy<n):
            if graph[xx][yy] == 1:
                dfs(xx, yy)
                cnt += 1


n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int, input())))

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

cnt_array = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            cnt = 1
            dfs(i, j)
            cnt_array.append(cnt)

print(len(cnt_array))
cnt_array.sort()
for x in cnt_array:
    print(x)

점점 잘 풀리니까 재밌당