프로그래머스 - 무인도 여행 (Python)

lv. 2 단계의 코딩 테스트 연습 문제 중 '무인도 여행'에 대한 풀이를 설명하고 있습니다.

 

프로그래머스 - 무인도 여행 (Python)

 

코딩 테스트 연습 문제 풀이

 

1. 원리

2. 코드

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 원리는 아주 간단하다.
• BFS를 사용하고, Visited로 방문한 곳을 체크만 잘하면 된다.

무인도 지도
X	1	1
X	1	1
1	X	X

• 위와 같이 무인도가 주어졌을 때, 먼저 우리는 이 무인도 지도 사이즈만큼의 Visited 배열을 만든다.

Visited
False	False	False
False	False	False
False	False	False

• 그리고 무인도 지도의 (0, 0)에서부터 (2, 2)까지 한 칸씩 순회하다가 방문하지 않은 무인도를 발견하게 되면 해당 칸에서부터 BFS 탐색을 시작한다.

무인도 지도
X	1	1
X	1	1
1	X	X

Visited
False	False	False
False	False	False
False	False	False

• (0, 1)이 해당 칸이므로 상하 좌우로 BFS를 탐색하면서 무인도 칸에 있는 식량들을 0으로 초기화된 totalFood에 더한다.

Visited
False	True	True
False	True	True
False	False	False

• 그러면 이렇게 변하고, totalFood = 4가 된다.
• 이렇게 구해진 totalFood를 answer 배열에 추가한다.
• 그러고 나서 다시 무인도 지도에서 무인도이면서 visited가 False인 칸을 다시 탐색을 이어가다보면 (0, 2) 칸에 도달한다.

무인도 지도
X	1	1
X	1	1
1	X	X

• 해당 칸에서 위와 같이 BFS를 돌리는 식으로 알고리즘을 이어가면 된다.
• 마지막에 오름차순 정렬이므로 answer를 오름차순으로 정렬한다.
• 이 부분에 해당하는 코드는 아래와 같다.

for i in range(len(maps)):
    for j in range(len(maps[0])):
        if not visited[i][j] and maps[i][j] != 'X':
            ## BFS 시작
            queue = deque()
            queue.append([i, j])
            totalFood = 0
            while queue:
                data = queue.popleft()
                cx = data[0]
                cy = data[1]
                if visited[cx][cy]:
                    continue
                visited[cx][cy] = True
                totalFood += int(maps[cx][cy])

                for k in range(4):
                    nx = cx + dx[k]
                    ny = cy + dy[k]
                    if check(nx, ny, len(maps), len(maps[0])) and maps[nx][ny] != 'X':
                        queue.append([nx, ny])
            answer.append(totalFood)

• 여기서 dx, dy는 상하좌우로 이동할 칸을 가지고 있는 배열이다.
• 전체 코드는 아래와 같다.
• check()는 이동한 칸이 지도 바깥인지 아닌지를 확인해주는 함수이다.

코드

from collections import deque

def check(x, y, maxX, maxY):
    if x < 0 or y < 0 or x >= maxX or y >= maxY:
        return False
    return True

def solution(maps):
    answer = []
    visited = [[False for _ in range(len(maps[0]))] for _ in range(len(maps))]
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    for idx, row in enumerate(maps):
        maps[idx] = list(row)

    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if not visited[i][j] and maps[i][j] != 'X':
                ## BFS 시작
                queue = deque()
                queue.append([i, j])
                totalFood = 0
                while queue:
                    data = queue.popleft()
                    cx = data[0]
                    cy = data[1]
                    if visited[cx][cy]:
                        continue
                    visited[cx][cy] = True
                    totalFood += int(maps[cx][cy])

                    for k in range(4):
                        nx = cx + dx[k]
                        ny = cy + dy[k]
                        if check(nx, ny, len(maps), len(maps[0])) and maps[nx][ny] != 'X':
                            queue.append([nx, ny])
                answer.append(totalFood)
    answer.sort()
    if len(answer) == 0:
        answer.append(-1)
    return answer

 

BFS 문제는 이제 많이 풀다보니 쉬워진 것 같다. 비슷한 문제를 백준에서 풀은 적이 있기에 더욱 빨리 풀 수 있었다.