[Python]FloodFill[Programmerレベル3]


問題の説明


n x mサイズの図面に描画された図の色を2次元リストとする.同じ色が同じ数字で表示されている場合、図に全部で何個の領域があるか知りたいです.領域とは上下左右に接続された同じ色の空間を指す.
例えば、リスト[1,2,3],[3,2,1]は、以下のように表すことができる.

この図には5つの領域があります.
画用紙の大きさnとmを画用紙に塗った色画像を与える場合は、resolution関数を書いて、図のいくつかの領域を返します.

せいげんじょうけん

  • nおよびmは、1または250以下の整数である.
  • 図の色は、1または30000未満の整数にすぎない.
  • I/O例
    nmimages正解23[1,2,3],[3,2,1]532[1,2],[1,2],[4,5]4
    I/O例#1
    前に述べたように.
    I/O例#2
    与えられた画像は、以下のように表すことができる.

    したがって、この画像には4つの領域が含まれています.
    これはBFSまたはDFSを使用する問題です.
    DFS=深度優先ナビゲーション->再帰関数の使用
    Pythonからコールタイムアウトに戻る
    尾部再帰コンパイラ自己最適化/Python提供X
    Pythonでは再帰呼び出しが遅いので、なるべくBFSを利用した方が良いでしょう.
    キューアルゴリズム
    
    from collections import deque
    
    def solution(n, m, image):
        
        answer = 0 
        
        # 오른쪽, 왼쪽, 위, 아래 이동
        # 코드를 간결하게 하기 위해 방향 처리 변수 directions에서 처리
        directions = [(0,1),(0,-1),(-1,0),(1,0)]
        
        for sy in range(n):
            for sx in range(m):
                if image[sy][sx] == float('inf'):
                    continue            
                target_color = image[sy][sx]
                queue = deque([(sy,sx)])
                            
                while queue:
                    
                    y, x = queue.popleft() # list의 pop은 시간복잡도 O(N)이기 때문에 O(1)로 하기 위해 DEQUE 사용
                    
                    for dy, dx in directions:
                        py = y + dy
                        px = x + dx
                        if px >= m or px < 0 or py >= n or py < 0:
                            continue
                        
                        if image[py][px] == target_color:
                            image[y + dy][x + dx] = float('inf')
                            queue.append((y+dy, x+dx))
    
                answer += 1
                
        return answer