[Algorithms] 깊이/넓이 우선 탐색 (DFS, BFS) 활용-단지 번호 붙이기(DFS, BFS 2가지 방법으로)

 

 

 

• 고민했던 점 1 : 하나의 그룹 안에서 다 돌고 이제 더이상 갈 곳이 없을 때, 다음 그룹으로 어떻게 이동할 것인가? 
  • 해결 : 이미 방문한 곳은 0으로 바꾸어 놓을 것이니, 격자를 이중 for문으로 하나하나 돌리면서 아직 1번으로 표시된 곳에서부터 DFS를 돌리면 된다
• 고민했던 점 2 : 집을 어떻게 카운팅 할 것인가?
  • 해결 : 이중 for문 안에서 DFS 시작 전에 cnt = 0으로 해주어, for 문 돌면서 각 그룹당 cnt를 진행할 수 있게끔 해준다. 카운팅 결과는 리스트 안에다 차곡차곡 append 해준다 

def DFS(x, y):
 
    global cnt
    cnt += 1
    apt[x][y] = 0
 
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0 <= xx < n and 0 <= yy < n and apt[xx][yy]==1:
            DFS(xx, yy)
 
 
 
if __name__=='__main__':
 
    n = int(input())
    apt = [list(map(int, input())) for _ in range(n)]       # 입력 값이 붙어 있는 케이스이므로 int로 mapping 해준 후 리스트화 해야한다
 
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
 
    res = []
    for i in range(n):              # 이렇게 for문을 돌면서
        for j in range(n):
            if apt[i][j] == 1:      # 아직 1로 표시되어 있는 부분을 찾아서 DFS를 진행한다
                cnt = 0             # 각 그룹당 count를 진행한다
                DFS(i, j)
                res.append(cnt)     # 한 그룹에서 나온 결과 cnt를 리스트에 저장
 
    print(len(res))
    res.sort()
    for x in res:
        print(x)
 
 
 

 

 

 

 

이번에는 BFS를 이용해서 풀어보자 

def BFS():
 
    global cnt
 
    while queue:
        now = queue.popleft()
        for i in range(4):
            xx = now[0] + dx[i]
            yy = now[1] + dy[i]
            if 0 <= xx < n and 0 <= yy < n and apt[xx][yy] == 1:
                apt[xx][yy] = 0
                cnt += 1
                queue.append((xx, yy))
 
 
 
if __name__=='__main__':
 
    n = int(input())
    apt = [list(map(int, input())) for _ in range(n)]       # 입력 값이 붙어 있는 케이스이므로 int로 mapping 해준 후 리스트화 해야한다
 
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
 
    res = []
    for i in range(n):
        for j in range(n):
            if apt[i][j] == 1:
                queue = deque()
                queue.append((i, j))
                apt[i][j] = 0
                cnt = 1
                BFS()
                res.append(cnt)
 
    print(len(res))
    res.sort()
    for x in res:
        print(x)