[Python] 프로그래머스 - 무인도 여행 파이썬 풀이

import sys

sys.setrecursionlimit(10000)

def dfs(x, y, maps, visit):
    val = 0

    if x < 0 or x >= len(maps[0]): return val
    if y < 0 or y >= len(maps): return val
    if visit[y][x] is True: return val
    if maps[y][x] == "X": return val

    visit[y][x] = True
    return int(maps[y][x]) + dfs(x - 1 , y, maps, visit) + dfs(x + 1 , y, maps, visit) + dfs(x, y - 1, maps, visit) + dfs(x, y + 1, maps, visit)

def solution(maps):
    answer = []
    ylen = len(maps)
    xlen = len(maps[0])
    visit = [[False] * xlen for _ in range(ylen)]

    for x in range(xlen):
        for y in range(ylen):
            if maps[y][x] == "X": continue
            if visit[y][x] is True: continue

            cs = dfs(x, y, maps, visit)

            if cs > 0: answer.append(cs)
    if len(answer) == 0: answer.append(-1)
    else: answer.sort()

    return answer

문제는 생략...

 

특정 지점에서 모든 연결점을 확인하고 연결된 점들끼리 값의 총합을 찾는 문제

모든 연결점 -> 모든 지점을 확인하는 완전탐색 -> dfs or bfs를 선택

문제 제한 조건에서 행과 열의 최대 100이었기에 O(n^2) 최악의 경우 10000 이하의 노드를 확인하므로 완전 탐색 가능하다.

 

고려사항

1. 문제의 조건인 'X' 값이라면 건너 뜀.

2. 이미 방문한적이 있다면(visit array 가 true 라면) 건너 뜀.

3. 조건의 영역을 벗어난다면 건너 뜀.

4. dfs 선택 시 최대 깊이 10000까지 갈 수 있으므로 최소 recursionlimit은 10000 이상을 해줌(파이썬의 경우).

5. 현 지점에서 4방향을 모두 확인하고 추가적으로 봐야할 지점이 존재한다면 재귀적으로 확인하며 값을 누적해줌.

6. 조건에 일치하는 것이 아무것도 없을 경우 answer에 -1을 넣어줌.

7. 조건에 일치하는 것이 하나 이상일 경우, 숫자의 오름차순으로 정렬해줌.

 

이런 완전탐색의 경우, 나 처럼 방문 노드를 확인하는 visit 배열을 생성하지 않고 maps의 값을 음수화 시켜서 확인한다던지 하는 기법을 활용할 수도 있다.

하지만, 알고리즘에 완전히 익숙한 사람이 아니라면, 조금 더 직관적으로 알 수 있는 방법을 사용하는 것이 좋다고 생각한다.(주관적)

(기업 코테에서는 메모리는 크게 문제가 되지 않는다.)

 

결론.

문제를 보고 바로 풀이방법을 찾아냈지만, 오랜만에 풀이라서 생각보다 버벅였다.

사실 maps, visit의 노드 방문시 행 열(x와 y)를 거꾸로 입력했는데 찾는데 시간이 걸렸다... 감이 많이 떨어져있다...

높은 난이도가 아니라도 하루에 한 문제씩이라도 꾸준히 풀어봐야겠다.