코딩테스트 스터디 - 프로그래머스 무인도 여행 (python)
2023. 3. 8. 02:34ㆍ배움엔 끝이없다/알고리즘
문제
링크 : 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
반응형
'배움엔 끝이없다 > 알고리즘' 카테고리의 다른 글
코딩테스트 스터디 - 프로그래머스 파괴되지 않은 건물(C++) (0) | 2023.11.16 |
---|---|
코딩테스트 스터디 - 프로그래머스 금과 은 운반(python) (2) | 2023.03.17 |
코딩테스트 스터디 - 프로그래머스 스타수열 (python) (0) | 2023.02.28 |
코딩테스트 스터디 - 백준 25406번 : 식사 계획 세우기 (C++) (0) | 2023.01.31 |
코딩테스트 스터디 - 프로그래머스 이모티콘 할인행사 (python) (0) | 2023.01.26 |