SDeung01
commented
11 months ago 문제 2 : 무인도 여행
문제
메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 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] |
문제풀이
- BFS와 DFS 모두 접근이 가능한 문제...라고 하지만 아직 DFS가 익숙하지 않아 접근방법을 잘 모르겠다.
- 위에서 푼 문제1번의 풀이를 응용하여 BFS로 풀어보았다.
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
class Solution {
// 위치 정보를 가지는 내부 클래스
class Pos{
private int x;
private int y;
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
}
public int[] solution(String[] maps) {
int[][] newMap = newMap(maps);
int xLength = maps[0].length();
int yLength = maps.length;
int[] aroundX = {0, 0, -1, 1};
int[] aroundY = {-1, 1, 0, 0};
boolean[][] visited = new boolean[yLength][xLength];
Queue<Pos> posQ = new LinkedList<>();
// BFS로 탐색을 완료한 섬 하나의 음식 총량을 List에 담는다.
ArrayList<Integer> islandList = new ArrayList<>();
// [0,0] 좌표부터 탐색 시작점을 옮겨가며 BFS를 반복한다.
for(int y = 0; y < yLength; y++){
for (int x = 0; x < xLength; x++){
int sum = 0;
// 탐색시작점이 바다가 아니고 아직 탐색하지 않은 장소라면 BFS 시작
if(newMap[y][x] > 0 && !visited[y][x]){
// 시작지점 세팅
// 미리 큐에 담은 Pos가 없고, 탐색 시 큐를 모두 비울때까지 탐색하므로 시작시 큐는 항상 비어있다.
if(posQ.isEmpty()){
posQ.offer(new Pos(x,y));
visited[y][x] = true;
sum += newMap[y][x];
}
// BFS
while(!posQ.isEmpty()) {
Pos pos = posQ.poll();
for(int i = 0; i < 4; i++){
int expX = pos.x + aroundX[i];
int expY = pos.y + aroundY[i];
if(expX >= 0 && expX < xLength && expY >= 0 && expY < yLength){
if(newMap[expY][expX] == 0 || visited[expY][expX]) continue;
visited[expY][expX] = true;
sum += newMap[expY][expX]; // 탐색 중 발견한 음식의 양을 더함
posQ.offer(new Pos(expX, expY));
}
}
} islandList.add(sum);
}
}
}
Collections.sort(islandList);
int[] result = islandList.stream().mapToInt(i->i).toArray();
return islandList.isEmpty() ? new int[] {-1} : result;
}
// String 배열 형태의 maps를 문자 단위로 쪼갠 후 숫자로 변환하여 int 2차원 배열의 형태로 반환
// 음식(숫자)은 1~9까지이므로 음식이 없는 위치(바다, X)는 0으로 저장
private int[][] newMap(String[] maps){
int[][] newMap = new int[maps.length][maps[0].length()];
for(int y = 0; y < maps.length; y++){
for(int x = 0; x < maps[0].length(); x++){
char food = maps[y].charAt(x);
if(Character.isDigit(food)){
// 제한조건에 위배되지 않으므로 편의를 위해 .isDigit()을 사용하였으나
// 예상 못한 오류를 피하려면 1~9까지의 범위를 명확히 주는 것이 좋다.
newMap[y][x] = food - '0';
}else {
newMap[y][x] = 0;
}
}
} return newMap;
}
}회고
- 다른 사람이 DFS방식으로 푼 풀이를 가져왔다.
- 탐색의 분기를 나눌 필요 자체가 없는 문제다보니 DFS 방식임에도 불필요한 연산을 한 BFS보다 처리 속도가 훨씬 빨랐다.
import java.util.ArrayList; import java.util.Arrays;
class Solution {
static int[] dI = {1,0,-1,0};
static int[] dJ = {0,-1,0,1};
static ArrayList<Integer> arr = new ArrayList<>();
public int[] solution(String[] maps) {
int[][] map = new int[maps.length+2][maps[0].length()+2];
Boolean[][] visit = new Boolean[maps.length+2][maps[0].length()+2];
for(int[] temp: map) {
Arrays.fill(temp, 0);
}
for(Boolean[] temp: visit) {
Arrays.fill(temp, true);
}
Boolean flag =false;
for(int i = 1; i <= maps.length; i++) {
for(int j = 1; j <= maps[0].length(); j++) {
if(maps[i-1].charAt(j-1) == 'X') {
map[i][j] = 0;
}
else {
map[i][j] = maps[i-1].charAt(j-1) - '0';
visit[i][j] = false;
flag = true;
}
}
}
if(!flag) {
return new int[] {-1};
}
for(int i = 1; i <= maps.length; i++) {
for(int j = 1; j <= maps[0].length(); j++) {
if(map[i][j] > 0 && !visit[i][j]) {
DFS(visit, map, i, j,0);
}
}
}
int ans[] = new int[arr.size()];
for(int i = 0; i < arr.size(); i++) {
ans[i] = arr.get(i);
}
Arrays.sort(ans);
return ans;
}
int DFS(Boolean[][] visit, int[][] map, int i, int j, int depth) {
if(visit[i][j] || map[i][j] == 0) {
return 0;
}
visit[i][j] = true;
int ans = map[i][j];
for(int k = 0; k < 4; k++) {
ans += DFS(visit,map,i+dI[k],j+dJ[k], depth+1);
}
if(depth == 0) {
arr.add(ans);
}
return ans;
}}
문제 1 : 게임 맵 최단거리
이번에는 탐색 알고리즘 문제 중에서 BFS 위주로 풀어보았습니다. 알고리즘 설명을 보아도 도저히 구현하는 방법을 모르겠어서 다른 사람의 풀이를 참고한 후 일부 변형하여 다시 푼 문제입니다.
문제
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.
위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.
만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.
입출력 예
문제 풀이
회고
class Solution {
}