[Python] 프로그래머스 - 캔디팡

[문제]

 

[풀이]

def count_regions(grid):
    n = 7
    visited = [[False] * n for _ in range(n)]

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    
    def dfs(x, y, color):        
        visited[x][y] = True
        count=1
        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] == color:
                count+=dfs(nx, ny, color)
        return count

    region_count = 0

    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                count=0
                if dfs(i, j, grid[i][j]) >=3:  
                    region_count+=1
    return region_count


grid = [list(map(int, input().split())) for _ in range(7)]

print(count_regions(grid))

 

 

DFS를 사용할 때, 방문 여부를 주어진 배열에 표시할 수 없는 경우에는 방문 여부를 적어둘 배열을 추가적으로 생성해주고 갱신해가며 search를 진행한다.

 

또한 이 문제는 DFS가 몇번째 level까지 진행되는지를 체크해야 되기 때문에 인자에 count 변수를 추가해주었다. 함수가 호출될 때마다 count 변수가 갱신되어야 하기 때문이다. 리턴값이 count이므로 count+=dfs(...) 코드를 작성하였다.