[Python]FloodFill[Programmerレベル3]
6956 ワード
問題の説明
n x mサイズの図面に描画された図の色を2次元リストとする.同じ色が同じ数字で表示されている場合、図に全部で何個の領域があるか知りたいです.領域とは上下左右に接続された同じ色の空間を指す.
例えば、リスト[1,2,3],[3,2,1]は、以下のように表すことができる.
この図には5つの領域があります.
画用紙の大きさnとmを画用紙に塗った色画像を与える場合は、resolution関数を書いて、図のいくつかの領域を返します.
せいげんじょうけん
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
Reference
この問題について([Python]FloodFill[Programmerレベル3]), 我々は、より多くの情報をここで見つけました https://velog.io/@ithingv/FloodFill-프로그래머스-Level-3テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol