무인도 여행 (with Python3)

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

- 생각하기 -

이 문제를 읽고 요약해보면 하나의 구역을 중심으로 상하좌우를 연결했을 때 몇 개의 구역이 나오고? 각 구역마다 숫자의 합이 무엇인지 문제이다.

그렇다면 먼저 우리는 1 x 1 격자 형태에서 상하좌우로 움직인다는 문제를 봤을 때 생각할 수있는 방법은 2가지있다.

바로 BFS, DFS이다.

제가 알고리즘을 풀 때 이 두 개의 개념을 생각하는 방식은

BFS는 어떤 점에 연결 된 것중 최단 거리를 구할 수 있고,

DFS는 어떤 점에 연결 된 것중 면적을 구할 수 있다라고 생각한다.

(BFS와 DFS는 모르면 안되는 개념이니 꼭 검색해서 익혀두자.)

BFS

 

DFS

 

그러면 이 문제에서는 어떤 탐색기법을 써야할까?

한 점에서 연결되어있는 것을 모두 찾고 숫자를 모두 더한 값을 얻으면 되지 않은가?

그렇다면 최솟값과 관련이 없는거 같으니 DFS문제구나라고 방향을 잡고 생각을 해본다.

(물론, BFS로도 풀 수 있지만 나는 이렇게 생각하고 푼다. BFS도 모든 경로를 찾는

탐색기법인 것은 맞으니깐..)

DFS(i, j)

DFS(i, j + 1)

 

위 그림을 참조하여 DFS(x , y)를 (x, y)에서 연결되어있는 노드들의 값의 합을 얻는 함수라고 가정하자.

그럼 DFS(x, y)에서는 (x, y)점에서 상하좌우 중 'X'가 아닌 숫자일 때의 점을 DFS함수로 재귀시킨다.

 

이 말을 예시로 쉽게 생각해보자, 위에 그림 DFS(i, j)에서 (i, j)는 3을 가지고 상하좌우에서 우측에 점인 (i, j + 1)이 숫자를 가지므로 DFS(i , j + 1)를 호출해서 (i, j + 1)점에서의 연결되어있는 노드들의 값의 합을 구한다.

근데 DFS(i, j + 1)에서 다시 DFS(i, j)를 호출하면 이 프로그램은 영원히 동작할 것이다.

( (i, j) => (i,  j + 1) => (i, j) => (i, j + 1) => ... )

그렇다면 우리는 방문 정보를 담을 수 있는 배열을 이용해 방문했다면 방문못하도록 막아야 한다. (배열 값이 true이면 방문했다고 설정)

이렇게 모든 점이 방문할 때 까지 DFS함수를 이용하여 영역의 값들을 구한다.

- 구현하기 -

 

생각하기 단계에서 DFS함수를 구현한 뒤 얻었던 값들을 리스트에 담아 정렬하면 된다.

먼저 DFS함수에서 visited라는 2차원 배열을 이용해 방문 정보를 저장하고

(x, y)에서 상하좌우로 이동할 때 방문 여부와 문제에 주어진 격자 크기를 비교해 움직여서 영역을 찾아내면 된다.

++ 이 정도의 힌트를 가지고 직접 풀어보자 ++

 

from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

def solution(maps):
    answer = []
    N, M = len(maps), len(maps[0])
    visited = [[False for _ in range(M)] for _ in range(N)]
    
    def dfs(x, y):
        visited[x][y] = True
        result = int(maps[x][y])
        for d in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx, ny = x + d[0], y + d[1]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and maps[nx][ny] != 'X': result += dfs(nx, ny)
        return result

    for i in range(N):
        for j in range(M):
            if not visited[i][j] and maps[i][j] != 'X': answer.append(dfs(i, j))
    return sorted(answer) if len(answer) > 0 else [-1]