문제
n x m 크기의 도화지에 그려진 그림의 색깔이 주어짐
같은 색깔은 같은 숫자로 나타남
그림에 있는 영역의 개수 구하기
n, m은 1이상 250이하인 정수
그림의 색은 1이상 30,000 미만인 정수
입출력 예시
| n | m | images | result |
|---|---|---|---|
| 2 | 3 | [[1, 2, 3], [3, 2, 1]] | 5 |
접근
2차원 배열에서의 BFS문제이다.
아직 검사하지 않은 좌표에서 BFS를 이용하여 연결된 영역들을 검출한다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import queue
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
q = queue.Queue()
def solution(n, m, image):
answer = 0
for i in range(n):
for j in range(m):
if image[i][j] != -1:
data = image[i][j]
image[i][j] = -1
q.put([i,j])
image = bfs(data, image, n, m)
answer += 1
return answer
def bfs(data, image, n, m):
while not q.empty():
cur = q.get()
for x, y in zip(dx, dy):
nx = cur[0] + x
ny = cur[1] + y
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if image[nx][ny] != data:
continue
image[nx][ny] = -1
q.put([nx,ny])
return image