https://school.programmers.co.kr/learn/courses/30/lessons/154540
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
📌 - 무인도 여행 - 접근
이 문제는 map의 크기도 100으로 제한되어 있고,
상,하,좌,우를 이용하면서 해당하는 경로의 숫자를 전부 더해주는 방식이라 DFS, BFS 문제라고 생각했고
백준의 안전 영역이나 빙산 문제와 비슷하다고 생각해서 BFS로 풀었다.
- 0,0부터 N,M까지 전부 탐색하면서 방문체크
- 방문하지 않은 섬일때 BFS를 이용해서 인접한 섬들의 수를 더해주고 다시 방문체크
- 인접한 섬들을 모두 체크 한뒤 다시 반복문으로 방문하지 않은 섬들을 다시 체크
이렇게 반복해서 나온 수들을 answer배열에 넣어주고 정렬해서 출력하면 답이 나오게 된다
📌 - python으로 푼 코드
from collections import deque
def BFS(start,end,visited,island):
q = deque()
q.append((start,end))
visited[start][end] = True
dx = [0,0,1,-1]
dy = [1,-1,0,0]
result = int(island[start][end])
while q :
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=ny< len(island[0]) and 0<=nx<len(island) and not visited[nx][ny] and island[nx][ny] !='X':
visited[nx][ny] = True
q.append((nx,ny))
result += int(island[nx][ny])
return result
def solution(maps):
answer = []
island = [list(map(str,maps[i])) for i in range(len(maps))]
visited = [[False] * len(island[0]) for _ in range(len(island))]
for i in range(len(island)):
for j in range(len(island[0])):
if island[i][j] != 'X' and not visited[i][j]:
answer.append(BFS(i,j,visited,island))
if answer:
answer.sort()
else:
answer.append(-1)
return answer