[1스4코1파] #99. LV 2. 무인도 여행

gunny·2023년 4월 12일

4코1파 코딩테스트 코딩테스트 python 프로그래머스 무인도 여행 프로그래머스 무인도 여행 python

코딩테스트

목록 보기

99/530

[1스4코1파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 1명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

★축★하★
4코1파 -> 1스4코1파 (스위프트 개발자 1명 추가)
일명 스우파 아니고 스코파 ~!

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (99일차)
[4코1파] 2023.01.13~ (90일차)
[1스4코1파] 2023.04.12~ (1일차)

Today :

2023.04.12 [99일차]

프로그래머스 LV 2
무인도 여행
https://school.programmers.co.kr/learn/courses/30/lessons/154540

문제 설명

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

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

제한사항

3 ≤ maps의 길이 ≤ 100
3 ≤ maps[i]의 길이 ≤ 100
maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
지도는 직사각형 형태입니다.

입출력 예

입출력 예 설명

입출력 예 #1
위 문자열은 다음과 같은 지도를 나타냅니다.

연결된 땅들의 값을 합치면 다음과 같으며

이를 오름차순으로 정렬하면 [1, 1, 27]이 됩니다.

입출력 예 #2
위 문자열은 다음과 같은 지도를 나타냅니다.

섬이 존재하지 않기 때문에 -1을 배열에 담아 반환합니다.

문제 풀이 방법

일단 이런 map 문제들은 바로 경로 문제로
bfs나 dfs를 구해서 푸는 문제로 이해해서
bfs 이용해서 구했는데..
외않되?

잉.. 이상해서 bfs 를 따로 함수로 묶어서 실행하니까 됨

뭐가 .. 문제지?

내 코드

from collections import deque


def bfs(maps, visited, i, j, n, m):
    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    visited[i][j] = 1
    queue = deque([[i,j]])
    tmp = int(maps[i][j])

    while queue:
        x,y = queue.popleft()
        for direction in directions:
            nxt_x, nxt_y = x+direction[0], y+direction[1]

            if 0<=nxt_x<n and 0<=nxt_y<m and maps[nxt_x][nxt_y] != 'X':
                if not visited[nxt_x][nxt_y]:
                    visited[nxt_x][nxt_y] =1
                    tmp += int(maps[nxt_x][nxt_y])
                    queue.append([nxt_x, nxt_y])

    return visited, tmp

def solution(maps):
    answer = []
    visited = [[0]*len(maps[0]) for _ in range(len(maps))]

    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if not visited[i][j] and maps[i][j] != 'X':
                visited, ans = bfs(maps, visited, i, j, len(maps), len(maps[0]))
                answer.append(ans)
            
    return [-1] if not answer else sorted(answer)

증빙