https://school.programmers.co.kr/learn/courses/30/lessons/154540
문제요약
다음과 같은 조건을 만족하는 무인도의 지도가 있다.
- 지도는 1 x 1 크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있다.
- 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룬다.
- 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타낸다.
지도를 나타내는 문자열 배열 maps가 주어질 때, 각 섬에서 머물 수 있는 최대 일수를 배열에 오름차순으로 담아 return 하는 함수를 만들어보자. 만약 지낼 수 있는 무인도가 없다면 -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] |
문제풀이
위 그림은 첫번째 예를 나타낸 것이다. 완전탐색 문제이며 BFS 혹은 DFS 로 문제를 해결할 수 있다.
하나의 칸을 하나의 노드로 보고, 상 하 좌 우로 연결된 노드들이 연결되고, 이미 등장한 노드는 연결되지 않는다고 할 때, 하나의 섬은 트리형태를 할 것이기 때문이다. Java의 경우 재귀함수를 이용하여 DFS 방식으로 해결하였고, Python은 Queue를 이용하여 BFS 방식으로 해결하였다.
코드
Java
import java.util.*;
public class IslandTravel {
private boolean[][] visited;
private char[][] map;
public int[] solution(String[] maps) {
List<Integer> answer = new ArrayList<>();
visited = new boolean[maps.length][maps[0].length()];
map = new char[maps.length][maps[0].length()];
for (int i = 0; i < maps.length; i++) {
for (int j = 0; j < maps[0].length(); j++) {
map[i][j] = maps[i].charAt(j);
}
}
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
int temp = dfs(i, j);
if (temp > 0) answer.add(temp);
}
}
Collections.sort(answer);
return answer.isEmpty() ? new int[] { -1 } : answer.stream().mapToInt(i -> i).toArray();
}
private int dfs(int row, int col) {
if (row < 0 || row == map.length || col < 0 || col == map[0].length) return 0;
if (visited[row][col]) return 0;
if (map[row][col] == 'X') return 0;
int res = map[row][col] - '0';
visited[row][col] = true;
res += dfs(row, col + 1);
res += dfs(row + 1, col);
res += dfs(row - 1, col);
res += dfs(row, col - 1);
return res;
}
}Python
def solution(maps):
answer = []
visited = [[False for _ in range(len(maps[0]))] for _ in range(len(maps))]
queue = []
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] ## 상 하 좌 우
boundary = (len(maps), len(maps[0]))
for i, col in enumerate(maps):
for j, row in enumerate(col):
curr = (i, j)
if visited[i][j]:
continue
if _is_island(row):
queue.append(curr)
temp = 0
while queue:
pos = queue.pop(0)
visited[pos[0]][pos[1]] = True
temp += int(maps[pos[0]][pos[1]])
for d in directions:
next_sq = (pos[0] + d[0], pos[1] + d[1])
if not _check_boundary(next_sq, boundary):
continue
if not _is_island(maps[next_sq[0]][next_sq[1]]):
continue
if not visited[next_sq[0]][next_sq[1]] and not next_sq in queue:
queue.append(next_sq)
answer.append(temp)
answer.sort()
if not answer:
answer = [-1]
return answer
def _check_boundary(sq, boundary):
i, j = sq
i_max, j_max = boundary
return 0 <= i < i_max and 0 <= j < j_max
def _is_island(sq):
return sq != 'X'
