코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.
- IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
- 상세 설명 - 수원대학교(대학일자리 플러스센터)
LV.2 - 무인도 여행
앞서 공부한 DFS(깊이 우선 탐색)을 사용해 무인도 여행 문제를 풀어보겠다.
문제 설명
메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.
지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.
제한사항
- 3 ≤ maps의 길이 ≤ 100
- 3 ≤ maps[i]의 길이 ≤ 100
- maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
- 지도는 직사각형 형태입니다.
입출력 예
| maps | result |
|---|---|
| ["X591X","X1X5X","X231X", "1XXX1"] | [1, 1, 27] |
| ["XXX","XXX","XXX"] | [-1] |
입출력 예 설명
입출력 예 #1
위 문자열은 다음과 같은 지도를 나타냅니다.
연결된 땅들의 값을 합치면 다음과 같으며
이를 오름차순으로 정렬하면 [1, 1, 27]이 됩니다.
입출력 예 #2
위 문자열은 다음과 같은 지도를 나타냅니다.
섬이 존재하지 않기 때문에 -1을 배열에 담아 반환합니다.
코드
import sys
sys.setrecursionlimit(int(1e6))
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
cnt = 0
def DFS(r, c, n, m, maps):
global cnt
cnt += int(maps[r][c])
maps[r][c] = 'X'
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if nr >= 0 and nr < n and nc >= 0 and nc < m and maps[nr][nc] != 'X':
DFS(nr, nc, n, m, maps)
def solution(maps):
global cnt
n = len(maps)
m = len(maps[0])
answer = []
maps = [list(row) for row in maps]
for i in range(n):
for j in range(m):
if maps[i][j] != 'X':
cnt = 0
DFS(i, j, n, m, maps)
answer.append(cnt)
if answer:
return sorted(answer)
else:
return [-1]풀이
이 문제는 이전에 풀었던 DFS - 픽셀 수 구하기 문제와 매우 흡사하다.
먼저 이 문제는 구현을 한다고 해도 런타임 에러가 발생한다.
이 이유는 프로그래머스 자체에서 재귀에 대한 제한을 걸었기 때문이다.
따라서 아래 코드를 추가해 재귀의 제한을 완화해야한다.
import sys
sys.setrecursionlimit(int(1e6))- maps 리스트 안에 문자열형태로 묶여있기 때문에 먼저 리스트형태로 변경한다.
- 그 후,
maps의 모든 원소를 돌면서 무인도인지 확인한다. - 무인도라면 해당 무인도 영역의 총 식량 개수를 세기 위해
count를0으로 초기화시키고,DFS에 maps의 크기 n, m과 현재 좌표와 maps를 담아 호출한다. DFS는 호출되면 우선 현재 좌표는 무인도 영역이므로 바다로 변경해놓고, 해당 무인도 좌표의 식량을count에 더한다.- 그 후, 해당 좌표에 상하좌우 네 방향을 방향 배열
dr,dc를 이용해 지도를 벗어나지 않으면서 무인도인지 확인한다. - 만약
무인도라면 이동한 좌표인nr,nc좌표를 기준으로 DFS를 호출한다. - 모든 무인도 영역을 다 이동하면 전부 바다('X')으로 변경되어 있으며, 해당 무인도를 다 탐색한 것이므로
무인도의 총 식량 개수(count)를answer에 삽입한다. - 그렇게 모든
maps의 모든 원소를 돌아 바다로 변경한 뒤 각각의 무인도 영역의 식량 개수를 세 삽입한answer오름차순으로 정렬해return하고, 만약 무인도가 존재하지 않는다면return [-1]한다.
