[프로그래머스 / C++ / JAVA / Javascript ] 무인도 여행 [c++]

문제 설명

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 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. 지도는 1x1 크기의 사각형으로 이루어진 격자 형태
2. 각 칸에는 ‘X’ 혹은 1~9 의 수
   1. 숫자는 식량을 의미
3. 연결된 숫자의 합 = 해당 무인도에서 머물 수 있는 최대 일수

---

문제 해결 접근법

1. 지도를 순회하며 무인도 찾기 (숫자)
2. 무인도에 도달시, 해당 칸 기준 연결된 칸 탐색
3. 탐색하며 연결된 칸의 합 계산

---

코드

C++

#include <bits/stdc++.h>
using namespace std;

// 상, 하, 좌, 우 이동을 위한 방향 배열
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

// 방문 여부를 체크하기 위한 2차원 벡터
vector<vector<bool>> visited(101, vector<bool>(101, false));

// BFS 함수: 무인도 탐색 및 최대 체류 일수 계산
int bfs(int x, int y, vector<string>& maps) {
    int cnt = 0;
    queue<pair<int,int>> q;
    visited[x][y] = true;
    cnt += maps[x][y] - '0';
    q.push({x,y});

    while(!q.empty()) {
        int x1 = q.front().first;
        int y1 = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nx = x1 + dx[i];
            int ny = y1 + dy[i];

            if(nx < 0 || ny < 0 || nx >= maps.size() || ny >= maps[0].length()) continue;
            
            if(maps[nx][ny] != 'X' && !visited[nx][ny]) {
                q.push({nx,ny});
                visited[nx][ny] = true;
                cnt += maps[nx][ny] - '0';
            }
        }
    }
    return cnt;
}

// 주 해결 함수
vector<int> solution(vector<string> maps) {
    vector<int> answer;

    for(int i = 0; i < maps.size(); i++) {
        for(int j = 0; j < maps[i].length(); j++) {
            if(maps[i][j] != 'X' && !visited[i][j]) {
                answer.push_back(bfs(i, j, maps));
            }
        }
    }

    sort(answer.begin(), answer.end());
    
    if(answer.empty()) {
        answer.push_back(-1);
    }

    return answer;
}

주요 포인트:

1. BFS 구현:
   • queue를 사용하여 BFS 구현
   • 상, 하, 좌, 우 네 방향으로 탐색
   • 방문한 칸은 visited 배열로 체크
2. 문자열을 정수로 변환:
   • maps[nx][ny] - '0'를 사용하여 문자를 정수로 변환
3. 경계 체크:
   • if(nx < 0 || ny < 0 || nx >= maps.size() || ny >= maps[0].length()) continue;
   • 지도 밖으로 나가는 것을 방지
4. 결과 처리:
   • 모든 무인도의 최대 체류 일수를 answer 벡터에 저장
   • 오름차순 정렬 후 반환
   • 무인도가 없는 경우 -1 반환

 

++추가++

Javascript

 

function solution(maps) {
  var answer = [];
  const height = maps.length;
  const width = maps[0].length;
  const dx = [-1,1,0,0];
  const dy = [0,0,-1,1];

  const visited = Array(height).fill().map(() => Array(width).fill(false));


  function bfs(start){
    let q = [];
    q.push([start[0], start[1], maps[start[0]][start[1]]]);
    visited[start[0]][start[1]] = true;
    let totalCost = 0;
    while(q.length){
      let [curX, curY, cost] = q.shift();
      totalCost += parseInt(cost,10);

      for(let i = 0; i<4; i++){
        let nx = curX + dx[i];
        let ny = curY + dy[i];
        if(nx < 0 || ny < 0 || nx >= height || ny >= width) continue;
        if( maps[nx][ny] === "X") continue;
        if(visited[nx][ny]) continue;

        visited[nx][ny] = true;
        q.push([nx,ny, maps[nx][ny]]);
      }    
    }
    return totalCost;
  }

  for(let i = 0; i<height; i++){
    for(let j = 0; j<width; j++){
      if(!visited[i][j] && maps[i][j] !== "X"){
        let tmp = bfs([i,j]);
        answer.push(tmp);
      }
    }
  }
  answer.sort((a, b) => a - b);
  
  return answer.length ? answer : [-1];
}

 

JAVA

import java.util.*;

class Solution {

    int[] dx = {-1,1,0,0};
    int[] dy = {0,0,-1,1};
    int width, height;

    boolean[][] visited;

    public int bfs(int sx, int sy, String[] maps){
        Queue<int[]> q = new LinkedList<>();
        int temp = maps[sx].charAt(sy);
        q.add(new int[]{sx, sy, maps[sx].charAt(sy) - '0'});
        visited[sx][sy] = true;
        int total = 0;
        while(!q.isEmpty()){
            int[] current = q.poll();
            int x = current[0];
            int y = current[1];
            int cost = current[2];

            total += cost;

            for(int i = 0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || ny < 0 || nx >= height || ny >= width) continue;
                if(maps[nx].charAt(ny) == 'X') continue;
                if(visited[nx][ny]) continue;

                visited[nx][ny] = true;
                q.add(new int[]{nx, ny, maps[nx].charAt(ny) - '0'});
            }
        }
        return total;
    }
    public int[] solution(String[] maps) {


        height = maps.length;
        width = maps[0].length();
        visited = new boolean[height][width];

        List<Integer> sizeList = new ArrayList<>();
        for(int i = 0; i<height; i++){
            for(int j = 0; j<width; j++){
                if(!visited[i][j] && maps[i].charAt(j) != 'X'){
                    int tmp = bfs(i,j, maps);
                    sizeList.add(tmp);
                }
            }
        }

        Collections.sort(sizeList);
        int[] answer = new int[sizeList.size()];

        for(int i = 0; i<sizeList.size(); i++){
            answer[i] = sizeList.get(i);
        }

        return sizeList.isEmpty() ? new int[]{-1} : answer;
    }
}