On.

---

Algorithm

---

1. 수도코드

1) image를 순회했는지 확인하기 위한 visited 배열 생성

2) for문으로 [0, 0] 위치부터 탐색 시작 (bfs 사용)

3) queue를 deque에 start를 추가한 형태로 할당한다.

4) while 문으로 큐에 대기 중인 원소가 없을 때까지 반복시키기

5) 큐에서 현재위치(y, x) pop하기

6) for 문으로 현재위치에서 상,하,좌,우에 해당하는 인덱스 탐색

7) 상,하,좌,우 인덱스가 visited의 범위와 주어진 color와 같은지 판별

8) 합당하면 해당 visited의 인덱스에 1 할당

9) 다음 위치를 queue에 추가

10) 더이상 갈 곳이 없어서 큐에 대기중인 원소가 없다면 return 1 한다. (여기 까지가 bfs 구현부)

11) bfs로부터 리턴 받은 1을 count에 더한다.

2. 구현코드

from collections import deque

def bfs(start, image, visited):
    queue = deque([start])
    color = image[start[0]][start[1]]
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    while queue:
        y, x = queue.popleft()
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if 0 <= ny < len(image) and 0 <= nx < len(image[0]) and not visited[ny][nx] and image[ny][nx] == color:
                visited[ny][nx] = 1
                queue.append((ny, nx))
    
    return 1

def solution(n, m, image):
    visited = [[0] * m for _ in range(n)]
    cnt = 0
    for y in range(n):
        for x in range(m):
            if not visited[y][x]:
                cnt += bfs((y,x), image, visited)
    return cnt

3. 배운 점

• BFS는 주로 특정 범위를 탐색할 때(점점 퍼져나가는 경우)에 사용하면 좋고, 큐로 구현한다.

• DFS는 주로 백트랙킹, 경우의 수(순열, 조합)등 깊게 파고들 때(?) 사용하는 것이 좋고, 스택으로 구현한다.

• BFS, DFS를 구현하는 것은 비슷하나, 각각의 문제에 어떻게 적용하는지에 따라 조금씩 달라지는 것 같다. 문제를 많이 풀어봐야 적용하는 실력이 늘 것 같다!

---

Off.

---

프론트와 백을 넘나드는 리드 개발자가 되는 그날까지 🔥🔥🔥