DFS/BFS 완전정복기 3 -영역을 구분짓는 DFS/BFS-

1. 문제

 

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

2667번: 단지번호붙이기

 

 

0과 1로 이루어진 2차원 배열에서 1로만 이루어진 영역을 구분지어서

 

영역이 몇개인지, 혹은 각 영역이 이루는 땅의 개수?가 몇개인지 구하는 문제

 

모두 BFS/DFS로 해결할 수 있다

 

기본적으로 (0,0)부터 탐색을 시작해서 전체를 탐색하는게 BFS/DFS의 기본이기는 한데

 

이렇게 하면 문제가 상당히 어렵다

 

중간에 0을 만나면 어떻게 건너 뛰어서 다른 영역을 찾아야한다는게 그게 쉽지는 않아

 

이런 문제의 핵심 전략은 모든 좌표를 시작점으로 생각한다는 점이다.

 

그러면서 시작점에서 map값이 0이면 탐색하지 않고, 1이면 탐색을 시작해서 영역이 어느정도 크기인지 찾는다는 점

 

 

2. 나의 풀이

 

 

2-1) BFS

from collections import deque
from sys import stdin

def bfs(x,y,n,maps):
    
    queue = deque([(x,y)])

    cnt = 0

    if maps[y][x] == '0':
        
        return 0
    
    else:
        
        
        maps[y][x] = '0'
        
        cnt += 1
        
        while queue:
            
            x,y = queue.popleft()

            for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
                
                dx = x + ni
                dy = y + nj

                if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= n-1 and maps[dy][dx] == '1':
                    
                    queue.append((dx,dy))
                    maps[dy][dx] = '0'
                    cnt += 1
            
        return cnt
                    

    

n = int(stdin.readline())

maps = [list(stdin.readline().rstrip()) for _ in range(n)]

cnt_list = []

ans = 0

for y in range(n):
    
    for x in range(n):
        
        cnt = bfs(x,y,n,maps)

        if cnt != 0:

            cnt_list.append(cnt)
            ans += 1

cnt_list.sort()

print(ans)

for cnt in cnt_list:
    
    print(cnt)

 

n*n 배열을 모두 순회하여 시작점 좌표 (x,y)를 찾고, 거기서 bfs()함수를 수행한다

 

이걸 생각하는게 첫번째 전략임

 

사실 여기만 생각하면 나머지는 bfs/dfs 함수를 짜기만 하면 끝이라

 

for y in range(n):
    
    for x in range(n):
        
        cnt = bfs(x,y,n,maps)

        if cnt != 0:

            cnt_list.append(cnt)
            ans += 1

 

다음은 bfs 함수를 시작해서 (x,y)에서 maps값이 '0'이면 바로 0을 return하고 (탐색할 필요가 없음)

 

'1'이면 이 근방은 하나의 영역이 되므로 탐색을 시작함

 

그래서 n*n 배열 범위를 벗어나지 않고, maps값이 '1'인 곳이면 큐에 넣고 다시 방문하지 않도록 maps를 '0'으로 바꿔줌

 

탐색하면서 땅의 개수를 세어야하니까 cnt에 1을 더해줌

 

이렇게 하면 '0'으로 둘러싸인 주위 둘레를 만나기까지 '1'만 존재하는 하나의 영역만을 탐색하게 될 것이다.

 

모든 탐색이 끝나면 cnt를 return한다

 

그리고 시작점 for문을 다시 순회하면서, 언젠가는 다시 '1'이 되는 곳을 찾을 것이고 그 근방에서 '1'의 개수를 세는 영역 구분짓기를 수행할 것이다

 

 

2-2) DFS

 

from sys import stdin

def dfs(x,y,n):
    
    global d,maps
    
    maps[y][x] = '0'
    
    d += 1

    for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
    
        dx = x + ni
        dy = y + nj

        if dx >= 0 and dy >= 0 and dx <= n-1 and dy <= n-1 and maps[dy][dx] == '1':
            
            dfs(dx,dy,n)
                

n = int(stdin.readline())

maps = [list(stdin.readline().rstrip()) for _ in range(n)]

ans = 0

cnt_list = []

for y in range(n):
    
    for x in range(n):
        
        d = 0

        if maps[y][x] != '0':
        
            dfs(x,y,n)

        if d != 0:
            
            ans += 1
            cnt_list.append(d)

cnt_list.sort()

print(ans)

for cnt in cnt_list:
    
    print(cnt)

 

DFS로도 영역 구분짓기를 할 수 있는데, 역시 n*n배열에서 모든 x,y를 순회하여 시작점을 고려하는게 첫번째이고

 

for y in range(n):
    
    for x in range(n):
        
        d = 0

        if maps[y][x] != '0':
        
            dfs(x,y,n)

        if d != 0:
            
            ans += 1
            cnt_list.append(d)

 

 

그리고 탐색하면서 땅의 개수를 세야하니까, d=0으로 초기화하고 d를 dfs내에 global 변수로 지정해서 탐색하면서 d의 값을 증가시킬 예정

 

애초에 시작점의 maps 값이 '0'이면 탐색을 하지 않도록 하고 '0'이 아니면 dfs를 수행해서 d 값을 갱신시킨다

 

def dfs(x,y,n):
    
    global d,maps
    
    maps[y][x] = '0'
    
    d += 1

    for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
    
        dx = x + ni
        dy = y + nj

        if dx >= 0 and dy >= 0 and dx <= n-1 and dy <= n-1 and maps[dy][dx] == '1':
            
            dfs(dx,dy,n)

 

dfs는 그냥 기본 dfs랑 똑같다고 보면 된다

 

x,y에서 maps를 '0'으로 바꾸면서 방문처리하고, d를 1 증가시키면서 4방향 탐색을 수행한다

 

maps 범위를 벗어나지 않고 maps값이 '1'이면 방문 가능하니까 재귀경로 만들면서 탐색 수행

 

'0'을 만나면 방문하지 않고 재귀경로가 끊길거임

 

그래서 '0'으로 둘러싸인 '1'만 존재하는 하나의 영역을 찾고 d를 갱신한다음에..

 

다시 시작점 (x,y)를 찾는 식으로 반복하게 될 것

 

-------------------------------------------------------------------------------------------------------------------------------------------

 

 

3. 다른 문제2

 

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

 

1012번: 유기농 배추

 

이번엔 땅의 개수를 세는게 아니고 1로 이루어진 영역의 개수를 구하는 문제

 

 

2-1) BFS

 

위 문제랑 전혀 차이가 없음

 

이번엔 땅의 개수를 세는게 아니고 0으로 둘러싸인 하나의 영역을 모두 탐색만 하면 1을 return

 

from collections import deque
from sys import stdin

def bfs(x,y,maps,n,m):

    queue = deque([(x,y)])

    if maps[y][x] == 1:
        
        maps[y][x] = 0

        while queue:
            
            x,y = queue.popleft()

            for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
                
                dx = x + ni
                dy = y + nj

                if (dx >= 0 and dx <= m-1) and (dy >= 0 and dy <= n-1) and maps[dy][dx] != 0:
                    
                    queue.append((dx,dy))
                    maps[dy][dx] = 0
             
   
        return 1

    else:
        
        return 0
    

T = int(stdin.readline())

for _ in range(1,T+1):
    
    m,n,k = map(int,stdin.readline().split())

    maps = [[0]*m for _ in range(n)]

    for _ in range(k):
        
        x,y = map(int,input().split())

        maps[y][x] = 1
    
    ans = 0

    for y in range(n):
        
        for x in range(m):
            
            ans += bfs(x,y,maps,n,m)
    
    print(ans)

 

먼저 주어진 입력에 따라 maps를 완성하고, 역시 n*m 배열을 모두 순회하여 시작점 (x,y)를 모두 순회하는게 가장 기본

 

bfs()에 들어가서 maps값이 0이면 바로 0을 return하고, 1이면 탐색을 시작

 

방문처리해서 maps를 0으로 바꾸고, 4방향 탐색을 수행해서 n*m 배열 범위를 벗어나지 않고, maps가 1이면 큐에 그 좌표 를 넣는다

 

이게 가능하다면 1인 영역을 찾았으므로, 큐가 빌때까지 탐색을 하면, 0으로 둘러싸인 하나의 영역을 찾게 된 것이니까 1을 return하면 된다

 

 

2-2) DFS

 

DFS 함수가 조금 특이하게 생겼는데 심층분석해본다

 

from sys import stdin,setrecursionlimit

setrecursionlimit(10000)

def dfs(x,y,n,m,square):
    
    if x < 0 or x > m-1 or y < 0 or y > n-1:
        
        return False
    
    if square[y][x] == 1:
        
        square[y][x] = 0

        dfs(x+1,y,n,m,square)
        dfs(x,y+1,n,m,square)
        dfs(x-1,y,n,m,square)
        dfs(x,y-1,n,m,square)
        return True
    
    return False




T = int(stdin.readline())

for _ in range(T):
    
    m,n,k = map(int,stdin.readline().split())

    square = [[0]*m for _ in range(n)]

    for _ in range(k):
        
        x,y = map(int,stdin.readline().split())

        square[y][x] = 1
    
    ans = 0

    for y in range(n):
        
        for x in range(m):
            
            ans += dfs(x,y,n,m,square)
    
    print(ans)

 

입력에 따라 maps를 완성하고 n*m 배열을 모두 순회하여 시작점 (x,y)를 순회하는게 기본이다

 

dfs()함수가 조금 특이하게 생겼는데 0으로 둘러싸인 영역의 1의 개수를 세는게 아니라

 

그런 영역을 찾기만 하면 된다는 점이 중요하다

 

def dfs(x,y,n,m,square):
    
    if x < 0 or x > m-1 or y < 0 or y > n-1:
        
        return False
    
    if square[y][x] == 1:
        
        square[y][x] = 0

        dfs(x+1,y,n,m,square)
        dfs(x,y+1,n,m,square)
        dfs(x-1,y,n,m,square)
        dfs(x,y-1,n,m,square)
        return True
    
    return False

 

(x,y)가 만약에 n*m 배열 범위를 벗어나면 즉시 False를 return하여 재귀경로를 끊는다

 

만약 maps[y][x] = 1이라는 것은 영역 하나를 찾았다는 뜻이므로 방문처리해서 0으로 바꾸고

 

4방향 탐색을 시작한다

 

이러한 탐색 결과는 어떻게 되든 상관없이, 찾기만 하면 True를 return하는 것은 확정임

 

4방향 모두 탐색에 4개의 재귀경로 dfs(x+1,y), dfs(x,y+1), dfs(x-1,y), dfs(x,y-1)을 각각 수행

 

이 4개는 언젠가는 0을 만나면서 전부 False로 끝날거임

 

하지만 그러면서 영역 하나의 1을 모두 0으로 바꿔준다

 

아무튼 하나의 영역을 찾았으니까 True를 return

 

시작점 (x,y)의 maps값이 0이라면 if문을 수행하지 않고 바로 False를 return하면 다음 시작점을 검사할 수 있다