Part of your World

문제 설명

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 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

입출력 예 설명

입출력 예 #1

위 문자열은 다음과 같은 지도를 나타냅니다.

!https://user-images.githubusercontent.com/62426665/206862823-4633fbf1-c075-4d35-b577-26f504dcd332.png

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

!https://user-images.githubusercontent.com/62426665/209070615-ae568f20-cf06-4f88-8d4f-8e9861af2d36.png

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

입출력 예 #2

위 문자열은 다음과 같은 지도를 나타냅니다.

!https://user-images.githubusercontent.com/62426665/206863265-0a371c69-d4b5-411a-972f-bdc36b90c917.png

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

Depth-First Search (DFS) 알고리즘을 사용해서 각각의 무인도를 탐색하고, 그 무인도에 있는 식량의 총합을 구하면 된다. DFS를 사용하여 연결된 땅들을 하나의 그룹으로 묶고, 그룹 내부의 모든 숫자를 합해주는 작업을 반복하면 된다.

package LV2;

import java.util.ArrayList;
import java.util.Collections;

public class H154540 {
    private final int[] dx = {-1, 0, 1, 0};  // 상, 우, 하, 좌로 움직일 x 좌표
    private final int[] dy = {0, 1, 0, -1};  // 상, 우, 하, 좌로 움직일 y 좌표
    private boolean[][] visited;  // 해당 좌표를 방문했는지 저장하는 배열
    private String[] maps;  // 주어진 지도
    private int m, n;  // 지도의 행과 열의 개수
    private int day;  // 하나의 무인도에서 머무를 수 있는 최대 일수

    public int[] solution(String[] maps) {
        this.maps = maps;  // 지도를 클래스 변수에 저장
        this.m = maps.length;  // 행의 개수를 저장
        this.n = maps[0].length();  // 열의 개수를 저장
        this.visited = new boolean[m][n];  // 방문 배열을 생성
        ArrayList<Integer> result = new ArrayList<>();  // 결과를 저장할 리스트 생성

        // 지도의 모든 좌표를 순회
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                // 만약 방문하지 않았고, 무인도(숫자)라면
                if(!visited[i][j] && maps[i].charAt(j) != 'X'){
                    this.day = 0;  // 무인도에서 머무를 수 있는 일수를 0으로 초기화
                    dfs(i, j);  // dfs를 시작
                    result.add(this.day);  // 결과 리스트에 추가
                }
            }
        }

        // 만약 무인도가 하나도 없다면
        if(result.size() == 0) {
            return new int[]{-1};  // -1을 반환
        } else {
            int[] answer = new int[result.size()];  // 결과 배열을 생성
            Collections.sort(result);  // 결과 리스트를 정렬
            // 결과 배열에 리스트의 원소를 차례대로 넣음
            for(int i=0; i<result.size(); i++) answer[i] = result.get(i);
            return answer;  // 결과 배열을 반환
        }
    }

    // DFS 메소드
    public void dfs(int x, int y) {
        visited[x][y] = true;  // 해당 좌표를 방문했음을 표시
        day += maps[x].charAt(y) - '0';  // 무인도에서 머무를 수 있는 일수에 해당 좌표의 값을 더함

        // 상, 우, 하, 좌 순서로 방문 가능한지 확인
        for(int i=0; i<4; i++){
            int nx = x + dx[i];  // 다음 x 좌표
            int ny = y + dy[i];  // 다음 y 좌표
            // 만약 다음 좌표가 지도 내부에 있고,
            if(nx >= 0 && nx < m && ny >= 0 && ny < n){
                // 다음 좌표를 아직 방문하지 않았으며, 무인도(숫자)라면
                if(!visited[nx][ny] && maps[nx].charAt(ny) != 'X'){
                    dfs(nx, ny);  // dfs를 계속 진행
                }
            }
        }
    }
}

'maps' 문자열 배열을 받아 각 요소를 순회하며 무인도를 찾아내고, 각 무인도의 총 식량 양을 구하여 오름차순으로 정렬한 뒤 결과를 반환한다. 만약 무인도가 없다면 -1을 반환한다.

이 코드에서 DFS 함수는 각 좌표를 방문하고 4방향을 확인해서 이동 가능한 즉, 무인도인 좌표가 있는지 확인하고 있다. 이동 가능한 좌표가 있다면 해당 좌표를 다시 DFS 함수에 넣어 재귀적으로 방문하는 방식이다. 이 과정을 통해 연결된 무인도를 모두 탐색하고 그 식량 양을 합산할 수 있다.

문제 설명

완호가 관리하는 어떤 데이터베이스의 한 테이블은 모두 정수 타입인 컬럼들로 이루어져 있습니다. 테이블은 2차원 행렬로 표현할 수 있으며 열은 컬럼을 나타내고, 행은 튜플을 나타냅니다.

첫 번째 컬럼은 기본키로서 모든 튜플에 대해 그 값이 중복되지 않도록 보장됩니다. 완호는 이 테이블에 대한 해시 함수를 다음과 같이 정의하였습니다.

1. 해시 함수는 col, row_begin, row_end을 입력으로 받습니다.
2. 테이블의 튜플을 col번째 컬럼의 값을 기준으로 오름차순 정렬을 하되, 만약 그 값이 동일하면 기본키인 첫 번째 컬럼의 값을 기준으로 내림차순 정렬합니다.
3. 정렬된 데이터에서 S_i를 i 번째 행의 튜플에 대해 각 컬럼의 값을 i 로 나눈 나머지들의 합으로 정의합니다.
4. row_begin ≤ i ≤ row_end 인 모든 S_i를 누적하여 bitwise XOR 한 값을 해시 값으로서 반환합니다.

테이블의 데이터 data와 해시 함수에 대한 입력 col, row_begin, row_end이 주어졌을 때 테이블의 해시 값을 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ data의 길이 ≤ 2,500
• 1 ≤ data의 원소의 길이 ≤ 500
• 1 ≤ data[i][j] ≤ 1,000,000
  • data[i][j]는 i + 1 번째 튜플의 j + 1 번째 컬럼의 값을 의미합니다.
• 1 ≤ col ≤ data의 원소의 길이
• 1 ≤ row_begin ≤ row_end ≤ data의 길이

입출력 예

data col row_begin row_end result

입출력 예 설명

• 정해진 방법에 따라 튜플을 정렬하면 {4, 2, 9}, {2, 2, 6}, {1, 5, 10}, {3, 8, 3} 이 됩니다.
• S_2 = (2 mod 2) + (2 mod 2) + (6 mod 2) = 0 입니다.
• S_3 = (1 mod 3) + (5 mod 3) + (10 mod 3) = 4 입니다.
• 따라서 해시 값은 S_2 XOR S_ 3 = 4 입니다.

package LV2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class H147354 {
    public static int solution(int[][] data, int col, int row_begin, int row_end) {
        sort(data, col);
        List<Integer> modResult = getModResult(data, row_begin, row_end);
        return getXOR(modResult);
    }

    // 튜플의 col 번째 컬럼의 값을 기준으로 오름차순 정렬을 하되, 값이 동일하면 첫 번째 컬럼의 값을 기준으로 내림차순 정렬
    // data[i][j]는 i + 1 번째 튜플의 j + 1 번째 컬럼의 값을 의미합니다.
    private static void sort(int[][] data, int col) {
        Arrays.sort(data, (o1, o2) -> {
            if (o1[col - 1] == o2[col - 1]) {
                return o2[0] - o1[0];
            }
            return o1[col - 1] - o2[col - 1];
        });
    }

    // 정렬된 데이터에서 S_i를 i번째 행의 튜플에 대해 각 컬럼의 값을 i로 나눈 나머지들의 합으로 정의
    private static List<Integer> getModResult(int[][] data, int row_begin, int row_end) {
        List<Integer> result = new ArrayList<>();

        for (int i = row_begin; i <= row_end; i++) {
            int sum = 0;
            for (int j = 0; j < data[0].length; j++) {
                sum += data[i - 1][j] % i;
            }
            result.add(sum);
        }

        return result;
    }

    // row_begin <= i <= row_end 인 모든 S_i를 누적하며 XOR 한 값을 해시값으로 반환
    private static int getXOR(List<Integer> modResult) {
        int sum = modResult.get(0);

        for (int i = 1; i < modResult.size(); i++) {
            sum ^= modResult.get(i);
        }

        return sum;
    }
}

알고리즘

추상적이고 이상적인 절차를 기술한 것

구현에 필요한 세부 사항과 현실적인 고려 사항을 무시

알고리즘은 추상적이고 이상적인 절차를 기술한 것으로, 구현에 필요한 세부사항과 현실적인 고려사항을 무시한다. 알고리즘은 정확하고 명로한 레시피이다.

알고리즘은 결국 멈춰야 함

프로그램

실제 컴퓨터가 과제를 완료하기 위해 수행해야 하는 모든 단계를 구체적으로 서술

하나 이상의 알고리즘이 컴퓨터가 직접 처리할 수 있는 형태로 표현된 것

실직적인 문제도 신경 써야 함(메모리 부족, 제한된 프로세서 속도, 유효하지 않거나 악의적으로 잘못된 입력 데이터, 하드웨어 결함, 네트워크 연결 불량, 인간적인 약점)

실제 컴퓨터가 과제를 완료하기 위해 수행해야 하는 모든 단계를 구체적으로 서술한다. 불충분한 메모리, 제한된 프로세서 속도, 유효하지 않거나 악의적으로 잘못된 입력 데이터, 하드웨어 결함, 네트워크 연결 불량, 인간적인 약점 등의 문제가 포함된다.

알고리즘과 프로그램 사이에는 명확한 차이점이 있다.

알고리즘이란 문제를 해결하기 위한 일련의 정해진 절차를 의미한다. 개념적이고 추상적인 형태로 표현되며, 어떤 언어로도 표현될 수 있다. 알고리즘은 문제를 해결하는 방법을 구체적으로 정의하며, 주어진 입력에 대해 예상 가능한 출력을 제공해야 한다.

프로그램은 이 알고리즘을 특정 프로그래밍 언어로 구현한 것이다. 컴퓨터에 의해 실행될 수 있는 구체적인 코드입니다. 프로그램은 알고리즘을 실제로 동작하게 하는 방법에 초점을 맞추며, 이 과정에서 여러 현실적인 제약 사항을 고려해야 한다. 메모리 용량, 프로세서 속도, 입출력 데이터의 유효성, 하드웨어의 기능, 네트워크 상태 등이 포함된다.

따라서 알고리즘과 프로그램을 비교하면, 알고리즘은 이상적인 요리 레시피라고 볼 수 있다. 이 레시피는 어떤 요리사에게도 전달될 수 있으며, 재료와 조리 방법을 제공합니다. 반면, 프로그램은 이 레시피를 구체적으로 실행하는 요리사라고 할 수 있다. 요리사는 주방의 환경, 재료의 상태, 조리 도구 등의 실제 사항을 고려해야 한다.