[프로그래머스] 무인도 여행 (파이썬)

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

🔎메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다.

이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

출처: 프로그래머스

---

전형적인 dfs, bfs 문제였다.

 

maps와 그 원소들의 길이가 100이었고, 값이 'X' 또는 1~9사이 숫자로 조건도 완벽했다.

 

우선은 조금 더 친한 dfs를 통해서 문제를 해결하려고 시도했으나, 런타임 에러와 실패가 많이 떴다.

탐색 과정을 시각화해서 살펴봐도 내가 테스트한 케이스들에서는 잘 작동했다. 아마 탈출 조건에서 에러가 발생한 것 같지만, 아직까지 원인은 발견하지 못했다..

 

<틀린 코드 보기>

def solution(maps):
    answer = []
    r, c = len(maps), len(maps[0])
    maps = list(map(list, maps))
    visit = [[0]*c for _ in range(r)]
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

    def dfs(x, y, val):
        if visit[x][y] or maps[x][y] == 'X':
            return

        visit[x][y] = 1
        flag = 0

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < r and 0 <= ny < c and maps[nx][ny] != 'X' and not visit[nx][ny]:
                flag += 1
                dfs(nx, ny, val + int(maps[nx][ny]))

        if flag == 0:
            answer.append(val)


    for i in range(r):
        for j in range(c):
            if maps[i][j] != 'X':
                dfs(i, j, int(maps[i][j]))
    
    
    if answer:
        answer.sort()
        return answer
    else:
        return [-1]

그래서 bfs로 방향을 틀어 문제를 푸니까 맞았다.

 

<정답 코드>

from collections import deque
def solution(maps):
    answer = []
    r, c = len(maps), len(maps[0])
    maps = list(map(list, maps))
    visit = [[0] * c for _ in range(r)]
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

    def bfs(x, y):
        if visit[x][y] or maps[x][y] == 'X':
            return

        q = deque()
        q.append((x, y))
        visit[x][y] = 1
        val = 0
        while q:
            cx, cy = q.popleft()
            val += int(maps[cx][cy])

            for i in range(4):
                nx, ny = cx+dx[i], cy+dy[i]
                if 0 <= nx < r and 0 <= ny < c and not visit[nx][ny] and maps[nx][ny] != 'X':
                    q.append((nx, ny))
                    visit[nx][ny] = 1

        return val

    for i in range(r):
        for j in range(c):
            if maps[i][j] != 'X':
                life = bfs(i, j)
                if life:
                    answer.append(life)

    if answer:
        answer.sort()
        return answer
    else:
        return [-1]

접근은 아래와 같다.

1. 탐색이 좀 더 편하도록 maps의 원소를 list로 변환한다.
2. 문제에서 대각선을 포함하지 않았기 때문에, 대각선 방향을 제외한 4가지 방향을 dx, dy배열로 준비한다.
3. X가 아닌 지역에서 bfs를 수행한다. bfs를 마친 결과를 answer배열에 업데이트 한다.
4. answer 배열을 오름차순으로 정렬하여 return한다.

다시 보니 코드가 그렇게 깔끔하게 작성된 것 같진 않다. 

중복해서  점검하는 부분도 있는 것 같고, 좀 더 짧게 작성할 수 있었을 것 같다.