프로그래머스 - FloodFill

1. 문제

2. 소스코드 (Python3)

DFS 코드 (성공)

def inRange(n, m, i, j):     if i<0 or i>=n or j<0 or j>=m: return False     return True   def DFS(image, visit, n, m, i, j):     # 상하좌우     di = [-1, 1, 0, 0]     dj = [0, 0, -1, 1]         stack = [(i, j)]     while stack:         i1, j1 = stack.pop()         visit[i1][j1] = True         for d in range(4):             i2 = i1 + di[d]             j2 = j1 + dj[d]             if not inRange(n, m, i2, j2): continue             if visit[i2][j2]: continue             if image[i1][j1] == image[i2][j2]:                 stack.append((i2, j2))     return     def solution(n, m, image):     answer = 0     visit = [[False for j in range(m)] for i in range(n)]          for i in range(n):         for j in range(m):             if visit[i][j]: continue             answer += 1             DFS(image, visit, n, m, i, j)                 return answer

 

union-find 코드 (실패: 런타임 에러)

def find(parent, x):     if x == parent[x]:         return x     return find(parent, parent[x])   def union(parent, image1d, n, m, x, y):     x = find(parent, x)     y = find(parent, y)     if x > y:         parent[y] = x     else:         parent[x] = y   def inRange(n, m, i, j):     if i<0 or i>=n or j<0 or j>=m: return False     return True   def solution(n, m, image):     answer = 0     image1d = []     for i in range(n):         image1d += image[i]     parent = [i * m + j for i in range(n) for j in range(m)]     di = [0, -1]     dj = [-1, 0]     for i in range(n):         for j in range(m):             num1 = i * m + j             for d in range(2):                 if inRange(n, m, i+di[d], j+dj[d]):                     num2 = (i + di[d]) * m + (j + dj[d])                     if image1d[num1] == image1d[num2]:                         union(parent, image1d, n, m, num1, num2)     parentset = set()     for i in range(n):         for j in range(m):             parentset.add(find(parent, i*m+j))       return len(parentset)

3. 고찰

문제를 보자마자 union-find방식이 생각나서 문제를 풀었다.

테스트 케이스 뿐만 아니라 아래와 같이 특이한 케이스도 추가하여 성공하였다.

입력값 〉	4, 4, [[1, 1, 2, 1], [1, 3, 4, 1], [1, 1, 1, 1], [2, 3, 2, 3]]
기댓값 〉	8

그런데 채점을 하면 런타임 에러로 실패하였다.

그래서 검색을 통해 union-find를 DFS로 구현할 수 있다는 것을 알고 구현하여 성공하였다.

 

1) DFS코드 알고리즘

모든 원소에 대해서 반복한다.

    이미 방문한 원소이면 continue.

    DFS 방식으로 같은 색상의 영역만을 상하좌우로 탐색한다.

    새롭게 시작하는 원소의 개수를 세어 리턴.

 

2) DFS코드 시간복잡도

모든 원소에 대해서 반복 -> O(N^2)

    DFS함수는, stack에 쌓이는 만큼 4개의 방향에 대해 반복한다.

따라서 시간복잡도는 O(N^2)인 것 같다.

 

※ 원래의 DFS의 경우, 한 정점마다 한 번씩 호출되므로 V번(정점 개수) 호출되고,

모든 간선을 한번씩(방향 그래프인 경우) 또는 두번씩(무방향 그래프인 경우) 확인한다.

따라서 DFS의 시간복잡도는 O(V + E)이다.