방구석프로의 이야기

https://school.programmers.co.kr/learn/courses/30/lessons/12941

문제

문제 설명
길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.
배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
A에서 세번째 숫자인 2, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)
즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

제한사항
배열 A, B의 크기 : 1,000 이하의 자연수
배열 A, B의 원소의 크기 : 1,000 이하의 자연수
입출력 예
A B answer
[1, 4, 2] [5, 4, 4] 29
[1,2] [3,4] 10
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
A에서 첫번째 숫자인 1, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 4) 다음, A에서 두번째 숫자인 2, B에서 첫번째 숫자인 3을 뽑아 곱하여 더합니다. (누적된 값 : 4 + 6 = 10)
이 경우가 최소이므로 10을 return 합니다.

문제 해결을 위한 과정

곱의 합을 최소로 만들기 위한 핵심 아이디어는 "한 배열에서 가장 큰 값은 다른 배열에서 가장 작은 값과 곱해져야 한다는 것"입니다. 큰 수끼리 곱해지면 숫자가 기하급수적으로 커지기 때문입니다.

1. 배열 정렬: 두 배열 A와 B를 Arrays.sort()를 이용해 오름차순으로 정렬합니다.
2. 엇갈려 곱하기:
   • A 배열은 앞에서부터(작은 값부터) 탐색합니다: A[i]
   • B 배열은 뒤에서부터(큰 값부터) 탐색합니다: B[n - i - 1]
3. 결과 누적: 엇갈린 두 값을 곱한 뒤 answer에 더해줍니다. 이 행동을 배열의 길이만큼 반복하면 수학적으로 가장 작은 최솟값이 도출됩니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int []A, int []B) {
        int answer = 0;
        int n = A.length;
        
        Arrays.sort(A);
        Arrays.sort(B);
        
        for(int i = 0; i < n; i++) {
            answer += A[i] * B[n-i-1];
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/12951#

문제

문제 설명
JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고)
문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요.

제한 조건
s는 길이 1 이상 200 이하인 문자열입니다.
s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다.
숫자는 단어의 첫 문자로만 나옵니다.
숫자로만 이루어진 단어는 없습니다.
공백문자가 연속해서 나올 수 있습니다.
입출력 예
s return
"3people unFollowed me" "3people Unfollowed Me"
"for the last week" "For The Last Week"

문제 해결을 위한 과정

처음 이 문제를 처음 접할 때 s.split(" ")을 이용해 단어 배열을 만들고 접근하였고 Fail판정을 받았습니다. 그 이유는 다음과 같습니다.

1. 공백이 연속으로 나오는 경우: "3people    unFollowed me"처럼 단어 사이에 공백이 여러 개일 때
2. 문자열 마지막에 공백이 있는 경우: 자바의 기본 split은 문자열 맨 끝에 붙은 공백들을 무시하고 잘라버리기 때문에 원래 문자의 형태를 훼손합니다.

따라서 이 문제를 풀기 위해서는 문자열을 한 글자씩(charAt) 순회하면서 직접 처리해야 합니다.

문자열을 한 바퀴 돌면서 아스키코드(ASCII) 값을 기준으로 대소문자를 판별합니다.

1. 맨 첫 글자 (i == 0): 무조건 대문자가 되어야 하는 자리입니다. 소문자 범위(97 ~ 122)라면 아스키값에서 32를 빼서 대문자로 변환하고, 그 외(숫자나 대문자)라면 그대로 둡니다.
2. 그 외의 글자들 (i > 0):
   • 내 앞 글자가 공백(" ")인 경우: 새로운 단어의 시작점입니다. 즉, 대문자가 되어야 합니다. 현재 글자가 소문자라면 대문자로 바꾸고(num - 32), 원래 대문자나 숫자였다면 건드리지 않고 그대로(num) 붙여줍니다.
   • 내 앞 글자가 공백이 아닌 경우: 단어의 중간이나 끝에 끼어있는 글자들입니다. JadenCase 규칙상 첫 글자를 제외하곤 무조건 소문자여야 하므로, 대문자 범위(65 ~ 90)인 글자를 발견하면 32를 더해 소문자로 강제 변환합니다.

소스코드

import java.util.*;

class Solution {
    public String solution(String s) {
        String answer = "";
        
        for(int i = 0; i < s.length(); i++) {
            int num = s.charAt(i) + 0;
            if(i == 0) { // 처음
                if(num >= 97 && num <= 122) {
                    answer += (char)(num - 32);
                } else {
                    answer += (char)num;
                }
            } else { // 그 외
                if((" ").equals(String.valueOf(s.charAt(i-1)))) {
                    if(num >= 97 && num <= 122)
                        answer += (char)(num - 32);
                    else
                        answer += (char)(num);
                } else if(num >= 65 && num <= 90)
                    answer += (char)(num + 32);
                else {
                    answer += (char)num;
                }
            }
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/12939?language=java

문제

문제 설명
문자열 s에는 공백으로 구분된 숫자들이 저장되어 있습니다. str에 나타나는 숫자 중 최소값과 최대값을 찾아 이를 "(최소값) (최대값)"형태의 문자열을 반환하는 함수, solution을 완성하세요.
예를들어 s가 "1 2 3 4"라면 "1 4"를 리턴하고, "-1 -2 -3 -4"라면 "-4 -1"을 리턴하면 됩니다.

제한 조건
s에는 둘 이상의 정수가 공백으로 구분되어 있습니다.
입출력 예
s return
"1 2 3 4" "1 4"
"-1 -2 -3 -4" "-4 -1"
"-1 -1" "-1 -1"

문제 해결을 위한 과정

• 문자열 분리: s.split(" ")을 이용해 공백 문자 기준으로 숫자들을 잘라 배열에 담습니다.
• 데이터 타입 변환: 정렬과 크기 비교를 위해 문자열 배열을 순회하며 Integer.parseInt()로 숫자로 바꾼 뒤 ArrayList에 담아줍니다. (이 과정에서 음수 기호 -도 알아서 정수로 잘 변환됩니다.)
• 정렬: Collections.sort()를 사용해 오름차순으로 정렬합니다.
• 결과 조립: 정렬되었기 때문에 가장 첫 번째 값(index 0)이 최솟값, 가장 마지막 값(size - 1)이 최댓값이 됩니다. 이를 문자열로 이어 붙여 반환합니다.

소스코드

import java.util.*;

class Solution {
    public String solution(String s) {
        String answer = "";
        ArrayList<Integer> arr = new ArrayList<>();
        
        String[] sarr = s.split(" ");
        for(int i = 0; i < sarr.length; i++) {
            arr.add(Integer.parseInt(sarr[i]));
        }
        
        Collections.sort(arr);
        
        answer += String.valueOf(arr.get(0));
        answer += " ";
        answer += String.valueOf(arr.get(arr.size() - 1));
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=java

문제

문제 설명
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항
각 단어는 알파벳 소문자로만 이루어져 있습니다.
각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
begin과 target은 같지 않습니다.
변환할 수 없는 경우에는 0를 return 합니다.
입출력 예
begin target words return
"hit" "cog" ["hot", "dot", "dog", "lot", "log", "cog"] 4
"hit" "cog" ["hot", "dot", "dog", "lot", "log"] 0

문제 해결을 위한 과정

이 문제는 한 글자만 다른 단어들을 체인처럼 엮어 목표 단어까지 도달하는 가장 짧은 경로를 찾는 문제입니다.

가중치가 없는 그래프의 최단 거리를 구할 때는 BFS(너비 우선 탐색)가 정석입니다.

특히, 단계를 정확하게 세기 위해 큐의 크기(q.size())만큼 끊어서 한 레벨씩 처리하는 레벨 단위 BFS 방식을 적용했습니다.

1. 선제 예외 처리: target 단어가 words 배열 안에 없다면 애초에 변환이 불가능하므로 BFS를 시작하기도 전에 0을 리턴해 효율성을 챙깁니다.
2. 레벨 단위 카운팅: while문이 돌 때마다 answer += 1을 통해 단계를 먼저 올려주고, 현재 큐에 들어있는 개수(len)만큼만 내부 for문을 돌려 같은 깊이(레벨)의 단어들을 한꺼번에 꺼냅니다.
3. 조기 반환 (Early Return): 큐에서 꺼낸 단어(now)가 target과 일치하는 순간, 곧바로 값을 리턴하며 전체 탐색을 종료합니다.
4. 다음 변환 단어 탐색: 아직 방문하지 않은 단어 중, 현재 단어와 딱 한 글자만 다른 단어를 찾아 큐에 추가하고 방문 처리합니다. (두 글자 이상 다르면 조기에 break하여 연산을 최적화합니다.)

소스코드

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        int n = words.length;
        
        boolean flag = false;
        for(int i = 0; i < n; i++) {
            if(target.equals(words[i])) {
                flag = true;
                break;
            }
        }
        if(!flag) {
            return 0;
        }
        
        boolean[] visited = new boolean[n];
        Queue<String> q = new LinkedList<>();
        q.offer(begin);
        
        while(!q.isEmpty()) {
            int len = q.size();
            answer += 1;
            for(int k = 0; k < len; k++) {
                String now = q.poll();
                if(now.equals(target)) {
                    return answer - 1;
                }   
                for(int i = 0; i < n; i++) {
                    int temp = 0;
                    if(visited[i])
                        continue;
                    for(int j = 0; j < now.length(); j++) {
                        if(temp >= 2)
                            break;
                        if(now.charAt(j) != words[i].charAt(j)) {
                            temp += 1;
                        }
                    }
                    if(temp == 1) {
                        q.offer(words[i]);
                        visited[i] = true;
                    }
                }   
            }
        }
        
        return 0;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/1844

문제

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항
maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

입출력 예
maps answer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1

문제 해결을 위한 과정

1. Queue 준비: 방문할 노드 정보(x, y)를 담을 큐를 생성합니다.
2. 상하좌우 탐색: dx, dy 배열을 이용해 현재 위치에서 이동할 수 있는 4방향을 확인합니다.
3. 경로 값 갱신:
   • 맵 밖으로 나가지 않고, 벽(0)이 아니며, 처음 방문(1)하는 칸이라면 탐색을 이어갑니다.
   • 다음 칸의 값 = 현재 칸의 값 + 1을 통해 출발지점으로부터의 거리를 누적합니다.
4. 도착 여부 확인: BFS가 종료된 후, 상대 팀 진영(n-1, m-1)의 값이 처음 그대로(1)거나 벽(0)이라면 도달 불가능한 것으로 판단하여 -1을 리턴합니다.

소스코드

import java.util.*;

class Solution {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int n, m;
    
    static void bfs(int sx, int sy, int[][] graph) {
        Queue<Node> q = new LinkedList<Node>();
        q.offer(new Node(sx, sy));
        
        while(!q.isEmpty()) {
            Node node = q.poll();
            int x = node.x;
            int y = node.y;
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                    continue;
                else if(graph[nx][ny] == 1){
                    graph[nx][ny] = graph[x][y] + 1;
                    q.offer(new Node(nx, ny));
                }
            }
        }
    }
    
    static class Node {
        int x;
        int y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public int solution(int[][] maps) {
        int answer = 0;
        n = maps.length;
        m = maps[0].length;
        
        bfs(0, 0, maps);
        
        if(maps[n-1][m-1] == 0 || maps[n-1][m-1] == 1)
            return -1;
        else
            return maps[n-1][m-1];
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/43162

문제

문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항
컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
computer[i][i]는 항상 1입니다.
입출력 예
n computers return
3 [[1, 1, 0], [1, 1, 0], [0, 0, 1]] 2
3 [[1, 1, 0], [1, 1, 1], [0, 1, 1]] 1

문제 해결을 위한 과정

• 그래프 구축: computers 인접 행렬 데이터를 ArrayList<ArrayList<Integer>> 인접 리스트로 변환합니다.
• 전체 순회: 1번 컴퓨터부터 n번까지 차례대로 확인합니다.
• 방문하지 않은 노드 탐색:
  • 아직 방문하지 않은 컴퓨터를 발견하면, 해당 지점에서 BFS를 시작합니다.
  • 한 번의 BFS가 끝나면, 그 시작점과 연결된 모든 컴퓨터는 visited 처리가 됩니다.
• 카운트: BFS가 새롭게 시작되는 횟수가 곧 독립된 네트워크의 개수입니다.

소스코드

import java.util.*;

class Solution {
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    
    static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        visited[start] = true;
        q.offer(start);
        while(!q.isEmpty()) {
            int v = q.poll();
            System.out.print(v + " ");
            for(int i = 0; i < graph.get(v).size(); i++) {
                int y = graph.get(v).get(i);
                if(!visited[y]) {
                    visited[y] = true;
                    q.offer(y);
                }
            }
        }
    }
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[n + 1];
        for(int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }
        
        for(int i = 0; i < computers.length; i++) {
            for(int j = 0; j < computers[i].length; j++) {
                if(i == j) {
                    continue;
                } else {
                    if(computers[i][j] == 1) {
                        graph.get(i+1).add(j+1);
                        graph.get(j+1).add(i+1);
                    }
                }
            }
        }
        
        for(int i = 1; i < n + 1; i++) {
            if(!visited[i]) {
                bfs(i);
                answer += 1;
            }
        }
        
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=java

문제

문제 설명
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.
입출력 예
numbers target return
[1, 1, 1, 1, 1] 3 5
[4, 1, 2, 1] 4 2
입출력 예 설명
입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4
총 2가지 방법이 있으므로, 2를 return 합니다.

문제 해결을 위한 과정

중복 순열(Product)을 이용해 모든 경우의 수를 탐색하며 현재 문제를 해결하면 됩니다.

1. 기호 배열 생성: {"-", "+"}라는 두 가지 선택지를 준비합니다.
2. 중복 순열 생성: 숫자의 개수(num)만큼 기호를 뽑는 모든 조합을 만듭니다. (예: 숫자가 3개라면 ---, --+, -+- ... 등 2^n 가지)
3. 계산 수행 (calc): 생성된 기호 배열(arr)과 숫자 배열(numbers)을 매칭하여 총합을 구합니다.
4. 타겟 확인: 총합이 target과 일치하면 answer를 증가시킵니다.

소스코드

import java.util.*;

class Solution {
    static String[] a = {"-", "+"};
    static String[] arr;
    static int num;
    static int answer = 0;
    
    static int calc(String[] arr, int[] numbers) {
        int temp = 0;
        int sum = 0;
        
        for(int i = 0; i < num; i++) {
            if("-".equals(arr[i])) {
                temp = numbers[i] * -1;        
            } else {
                temp = numbers[i];
            }
            
            sum += temp;
        }
        
        return sum;
    }
    
    static void perm(int cnt, int[] numbers, int target) {
        if(cnt == num) {
            int result = calc(arr, numbers);
            if(result == target) {
                answer += 1;
            }
            return;
        }
        
        for(int i = 0; i < a.length; i++) {
            arr[cnt] = a[i];
            perm(cnt + 1, numbers, target);
        }
    }
    
    public int solution(int[] numbers, int target) {
        num = numbers.length;
        arr = new String[num];
        
        perm(0, numbers, target);
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/42898

문제

문제 설명
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항
격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
물에 잠긴 지역은 0개 이상 10개 이하입니다.
집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.
입출력 예
m n puddles return
4 3 [[2, 2]] 4

문제 해결을 위한 과정

1. DP 테이블 정의: dp[i][j]를 (i, j) 위치까지 올 수 있는 최단 경로의 개수로 정의합니다.
2. 웅덩이 처리: 웅덩이가 있는 곳은 -1로 표시하여 경로 계산에서 제외합니다.
3. 초기값 설정 (가장자리):
   • 첫 번째 행과 열은 위나 왼쪽에서 오는 경로가 하나뿐이므로 모두 1로 채웁니다.
   • 주의: 첫 행/열이라도 중간에 웅덩이가 있다면, 그 이후의 칸들은 절대 도달할 수 없으므로 0인 상태로 두어야 합니다. 
4. 점화식: dp[i][j] = dp[i-1][j] + dp[i][j-1]
   • 단, 위쪽(i-1)이나 왼쪽(j-1)이 웅덩이(-1)인 경우 해당 값은 0으로 취급하여 더합니다.
5. 나머지 연산: 숫자가 매우 커질 수 있으므로 더할 때마다 1,000,000,007로 나눈 나머지를 저장합니다

소스코드

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        
        int[][] dp = new int[n][m];
        for(int i = 0; i < puddles.length; i++) {
            int y = puddles[i][0] - 1;
            int x = puddles[i][1] - 1;
            
            dp[x][y] = -1;
        }
        
        for(int i = 0; i < n; i++) {
            if(dp[i][0] == -1)
                break;
            dp[i][0] = 1;
        }
        for(int j = 0; j < m; j++) {
            if(dp[0][j] == -1)
                break;
            dp[0][j] = 1;
        }
       
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(dp[i][j] != -1) {
                    if(dp[i][j-1] == -1 && dp[i-1][j] == -1) {
                        continue;
                    } else if(dp[i][j-1] == -1 || dp[i-1][j] == -1) {
                        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                    } else {
                        dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
                    }
                }
            }
        }
        
        answer = dp[n-1][m-1];
        return answer;
    }
}