코딩테스트 스터디 - 프로그래머스 무인도 여행 (python)

문제

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

프로그래머스

요약

2차원 배열 지도에 X 혹은 1자리 숫자가 주어진다.

인접한 숫자들끼리는 하나의 섬을 이루는데, 섬마다 숫자 총 합을 구해 오름차순으로 정렬 후 반환하면 된다.

의식의 흐름

맵을 전부 탐색하면서 숫자를 발견하면, 그 위치에서 BFS나 DFS를 시작해 섬의 숫자 총 합을 구하면 된다.

맵을 복사해 보관해야한다는 등 메모리 복사를 할 일이 없어 BFS를 하기로 선택했다.

한 숫자는 하나의 섬에만 속하므로, 숫자를 처리하고 나서는 해당 칸을 X로 만들어 visited처럼 사용할 수 있다.

구현

자료구조

BFS 사용시, State = 숫자의 위치 를 사용했다.

알고리즘

위에서 설명한대로, 맵을 탐색해 숫자를 발견하면 그 위치에서 BFS로 섬의 숫자 총 합을 구한다.

X가 아닌 곳을 한 번씩만 탐색하기 때문에 O(N^2)에 해결된다.

코드

이제 이런 단순 BFS나 DFS 문제는 쉽게 풀리는 것 같다 !

 

def bfs(i, j, wallmap):
    total = 0
    moves = [(0,1), (0,-1), (1,0), (-1,0)]
    queue = [(i,j)]
    while len(queue) > 0:
        pos = queue.pop(0)
        if wallmap[pos[0]][pos[1]] == 'X':
            continue
        total += int(wallmap[pos[0]][pos[1]])
        wallmap[pos[0]][pos[1]] = 'X'
        for move in moves:
            queue.append((pos[0]+move[0],pos[1]+move[1]))
    return total

def solution(maps):
    answer = []
    wallmap = []
    wallmap.append(list("X"*(len(maps[0])+2)))
    for i in range(len(maps)):
        wallmap.append(list("X" + maps[i] + "X"))
    wallmap.append(list("X"*(len(maps[0])+2)))
                   
    for i in range(1, len(maps)+1):
        for j in range(1, len(maps[i-1])+1):
            if wallmap[i][j] == 'X':
                   continue
            answer.append(bfs(i,j,wallmap))
    if len(answer) == 0:
        return [-1]
    else:
        answer.sort()
    return answer