[프로그래머스 코딩테스트]Level03 - FloodFill

Level 03 - FloodFill

문제 설명

n x m 크기 도화지에 그려진 그림의 색깔이 2차원 리스트로 주어집니다. 같은 색깔은 같은 숫자로 나타난다고 할 때, 그림에 있는 영역은 총 몇 개인지 알아내려 합니다. 영역이란 상하좌우로 연결된 같은 색상의 공간을 말합니다.
예를 들어, [[1,2,3], [3,2,1]] 같은 리스트는 다음과 같이 표현할 수 있습니다.
이때, 이 그림에는 총 5개 영역이 있습니다.
도화지의 크기 n과 m, 도화지에 칠한 색깔 image가 주어질 때, 그림에서 영역이 몇 개 있는지 리턴하는 solution 함수를 작성해주세요.

제한사항

• n과 m은 1 이상 250 이하인 정수입니다.
• 그림의 색깔은 1 이상 30000 미만인 정수로만 주어집니다.
  

입출력 예

|—|—|—|—| |n |m |images |정답| |2 |3 |[[1, 2, 3], [3, 2, 1]] |5| |3 |2 |[[1, 2], [1, 2], [4, 5]] |4|

풀이

bfs를 이용해 풀었다.
image를 시작 좌표 0,0에서 끝 좌표까지 모두 방문하면서,
만약 방문하지 않은 좌표라면 bfs 시작!
해당 좌표의 동서남북을 탐색하여 네 좌표들이 현재 좌표와 같은 색을 갖고있는지 체크한다.
같은 색을 가지고 있지 않다면 스택이 비워져 bfs가 종료되고, 같은 색을 가진 영역을 한번 쭉 돌아본 것이므로 cnt += 1해준다.(bfs가 한번 실행될때마다 영역+1)

# 도화지 크기: n*m
# 칠한 색깔 배열: image
def solution(n, m, image):
    cnt = 0 # 같은 영역 개수 카운트
    visited = [[-1]*m for _ in range(n)] # 방문했었는지 여부를 담는 배열
    stack = [] # 도화지의 각 위치 넣어서 사방면을 확인하기 위한 스택
    dir = [[0, 1], [0, -1], [1, 0], [-1, 0]] # 동서남북 사방면 좌표

    for i in range(n):
        for j in range(m):
            if visited[i][j] == -1: # 해당 좌표에 방문한적이 없으면
                stack.append([i, j]) # 스택에 현재 좌표 삽입
                visited[i][j] = 1 # 해당 좌표를 방문한 것으로 바꿔줌
                color = image[i][j] # 해당 좌표의 색을 저장함
                # bfs
                while stack:
                    xy = stack.pop() # 스택에 저장해둔 좌표를 꺼내서
                    for k in range(4): # 해당 좌표에서의 동서남북 탐색 
                        xx = xy[1] + dir[k][0] # 동서남북 x좌표
                        yy = xy[0] + dir[k][1] # 동서남북 y좌표 
                        if 0<=xx<m and 0<=yy<n and visited[yy][xx] == -1 and image[yy][xx] == color:
                            # 비교순서 주의!! 1.좌표가 n*m영역 안에 있는지 체크 2.방문하지 않았던 좌표인지 체크 3.현재 좌표와 같은 색인지 체크
                            visited[yy][xx] = 1 # 방문한 좌표로 체크
                            stack.append([yy, xx]) # 세 조건이 모두 맞아떨어진다면 스택에 추가하여 계속 영역 탐색
                cnt += 1# [i,j]에 대해 bfs 끝난 뒤 영역 수 증가
    return cnt
print(solution(2, 3, [[1, 2, 3], [3, 2, 1]]))