[프로그래머스][queue/BFS] FloodFill

1. 문제 설명 

 

 

 

 

2. 풀이 

 

0) 설명 

핵심은 매트릭스를 탐색하는 과정에서 같은 숫자가 가세로에 연이어 있으면

해당 뭉탱이를 하나로 카운트하고, 아니면 각각 카운트하는 함수를 짜는것 !

 

여기서 뭉탱이를 하나로 --> 부분에서 BFS 가 활용된다. 

 

1) BFS 

 start point 에서 가세로를 탐색했을 때, 같은 색깔이 나오면,

 해당 point를 다음 탐색 범위로 지정하고 재탐색  또같은 색깔이 있는지 확인 

 이렇게 애니팡처럼 같은 색깔 쭉쭉 탐색한뒤에 어느순간 끝나면, 1로 반환해준다.  

 가령 이 과정에서 3개의 point를 찾았다면, 이 뭉탱이는 1로 반환되어버림 (3이 아님)

 

2) 그리고 다시 새로운 start point 로 탐색한다. 

 

말 설명이 더 어려운거 같으니 코드로...

 

 

 

1) 첫번째 시도 - 답은 맞으나 런타임 에러 

 

from collections import deque


def bfs(start, images, visited, cnt):
    queue = deque()
    queue.append(start) # 4. 시작점 디큐에 담기 
    moves = ((0, 1), (0, -1), (-1, 0), (1, 0)) # 5. 방향키 설정 
    now_color = images[start[0]][start[1]]

    while queue :
        x,y = queue.popleft()
        visited[x][y] = 1  # 6. 시작점 방문 표시 완료
        
        for dx, dy in moves:  # 7. 상하좌우 for문으로 탐색 
            up_x, up_y = x+dx, y+dy 
            
            # 8. 만약 상하좌우 움직인게 매트릭스 범위 안넘으면서 / 탐색 아직 안된 좌표면서 / 색깔까지 같으면 !!!! --> 같은 블럭~
            if 0 <= up_x < len(images) and 0 <= up_y < len(images[0]) and visited[up_x][up_y] == 0 and images[up_x][up_y] == now_color:
                queue.append((up_x, up_y))  # 9. 해당 지점 기준으로 다시 탐색하도록 큐에 담기

 
    return 1

def solution(n,m,images): # n = row, m = col
    visited = [[0 for _ in range(m)] for _ in range(n)] # 1. 입력형태와 같은 방문매트릭스 맨들어
    cnt = 0

    for x in range(n): # row
        for y in range(m): # col
            if visited[x][y] == 0: # 2. 방문 안한 좌표라면 
                cnt += bfs((x,y),images,visited, cnt) # 3. BFS 탐색 !  # 10. 탐색 후 cnt 업데이트

    return cnt

 

위 설명에서 

1) 번 과정이 BFS 함수로 구현되었고 

2) 번 과정이 solution 함수로 구성되었다. 

 

우선 2)번 부터 설명하면 

 1. 입력형태와 동일한 방문 매트릭스를 만듦

((가세로 포문돌리면서 하나씩 탐색 - 2중 포문 불가피함 ㅠ))

 2. 방문 안한 좌표라면 ! 

 3. 해당 지점 start 포인트로 해두고 BFS 탐색 

 

*** 여기서 BFS 함수의 역할은 

 start 포인트의 상하좌우 탐색하고, 같은 색깔나오면 방문 매트릭스 1로 채워줌 탐색 다 되면 1 반환

 따라서  start 포인트와 같은 색깔이 연이어 3개가 붙어있다면 

 3개 좌표는 다 탐색이 되었다고 표시가 되고 / 카운트는 1만 축적되는것  (애니팡 개념) 

 

 

1)번은 

4. 시작점 디큐에 담기 

5. 방향키 만들기 (--> 이 방법은 탐색 문제에서 항시 쓰이는 코드니 익숙해질것 ) 

6. 탐색 전 시작점 방문했다고 표시해놓기 

7. 상하좌우 for문으로 탐색 

8. 만약 상하좌우 움직인게 매트릭스 범위 안넘으면서 / 탐색 아직 안된 좌표면서 / 색깔까지 같으면 !!!! --> 같은 블럭~

9. 해당 지점 기준으로 다시 탐색하도록 큐에 담기 

 

*** 89번이 BFS 알고리즘에 핵심이다. 

BFS는 같은 층의 트리 노드를 모두 탐색하도록 큐에 넣어두고, 선입 선출하는 구조 

해당 문제에서는 같은 색깔의 포인트들을 모두 탐색하도록 디큐 자료구조에 넣어두고, popleft 로 맨앞의 포인트 뽑는

같은 개념이다 !!! 

 

 

10. 마지막으로 start 포인트와 같은 색깔이며 연결된 노드들을 다 탐색한 뒤에 한번 탐색했다고 반환해주는 것이다. 

 

 

 

하지만 !!!! 왜 런타임 에러가 떴나?

연결된 노드들을 탐색한 뒤에 해당 노드들도 탐색했다고 방문 매트릭스에 표시를 안했다.....

이걸 안하면, 이미 방문한 애들도 다시 BFS 를 타고들어가 8번까지 진행되고 다시 돌아가는 

무의미한... 재귀가 반복되는것....

 

 

 

 

2) 최종답안 !!! 

from collections import deque


def bfs(start, images, visited, cnt):
    queue = deque()
    queue.append(start) # 4. 시작점 디큐에 담기 
    moves = ((0, 1), (0, -1), (-1, 0), (1, 0)) # 5. 방향키 설정 
    now_color = images[start[0]][start[1]]

    while queue :
        x,y = queue.popleft()
        visited[x][y] = 1  # 6. 시작점 방문 표시 완료
        
        for dx, dy in moves:  # 7. 상하좌우 for문으로 탐색 
            up_x, up_y = x+dx, y+dy 
            
            # 8. 만약 상하좌우 움직인게 매트릭스 범위 안넘으면서 / 탐색 아직 안된 좌표면서 / 색깔까지 같으면 !!!! --> 같은 블럭~
            if 0 <= up_x < len(images) and 0 <= up_y < len(images[0]) and visited[up_x][up_y] == 0 and images[up_x][up_y] == now_color:
                queue.append((up_x, up_y))  # 9. 해당 지점 기준으로 다시 탐색하도록 큐에 담기
                visited[up_x][up_y] = 1 # !!!!! 방문했다고 방문 매트릭스 업데이트
 
    return 1

def solution(n,m,images): # n = row, m = col
    visited = [[0 for _ in range(m)] for _ in range(n)] # 1. 입력형태와 같은 방문매트릭스 맨들어
    cnt = 0

    for x in range(n): # row
        for y in range(m): # col
            if visited[x][y] == 0: # 2. 방문 안한 좌표라면 
                cnt += bfs((x,y),images,visited, cnt) # 3. BFS 탐색 !  # 10. 탐색 후 cnt 업데이트

    return cnt

 

 

1. 입력형태와 동일한 방문 매트릭스를 만듦((가세로 포문돌리면서 하나씩 탐색 - 2중 포문 불가피함 ㅠ))

2. 방문 안한 좌표라면 ! 

3. 해당 지점 start 포인트로 해두고 BFS 탐색 

4. 시작점 디큐에 담기 

5. 방향키 만들기 (--> 이 방법은 탐색 문제에서 항시 쓰이는 코드니 익숙해질것 ) 

6. 탐색 전 시작점 방문했다고 표시해놓기 

7. 상하좌우 for문으로 탐색 

8. 만약 상하좌우 움직인게 매트릭스 범위 안넘으면서 / 탐색 아직 안된 좌표면서 / 색깔까지 같으면 !!!! --> 같은 블럭~

9. 해당 지점 기준으로 다시 탐색하도록 큐에 담기 

!!!! 방문한 지점 방문 매트릭스 업데이트 !!!!! --> 런타임 에러 방지 

10. 마지막으로 start 포인트와 같은 색깔이며 연결된 노드들을 다 탐색한 뒤에 한번 탐색했다고 반환해주는 것이다. 

 

 

 

## BFS 추가설명 

BFS는 같은 층의 트리 노드를 모두 탐색하도록 큐에 넣어두고, 선입 선출하는 구조 

라고 러프하게만 설명했는데,

이 링크를 참고하면 이해하는데 도움이 될거같슴다 !

https://sarah950716.tistory.com/13

[그래프] BFS(너비우선탐색)

 

 

 

3. 정리 

매트릭스 탐색 같은 더러운문제... 

BFS DFS 라 생각하고 접근...

BFS 큐 선입선출 

DFS 스택 선입후출 

잊지마ㅏ.....ㅈㅔ발....