Computer Science Knowledge Storage

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

해당 문제는 검은색 선을 따라서만 이동할 수 있다는 것이 포인트였습니다.
예를 들어, 도형의 변이 다음과 같을 때 BFS/DFS를 할 때에 문제가 발생할 수 있습니다.
(4,3) -> (4,4) -> (5,3) -> ...
왜냐하면 저희가 현재까지 사용했던 dx/dy 테크닉을 사용하게 되면 (4,3)에서 (5,3)으로 바로 이동할 수 있기 때문입니다.

따라서 저는 Scale(2)을 두어 더 정교하게 이동할 수 있도록 하였습니다.
나중에 답을 구할 때에도 Scale의 값만큼 나누어줘야하는 주의사항이 있습니다.

소스코드

import java.util.*;

class Solution {
    
    int answer = 0;
    final int SIZE = 101;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    int[][] map = new int[SIZE][SIZE];
    boolean[][] visited = new boolean[SIZE][SIZE];
    Queue<Pair> q = new LinkedList<>();
    
    class Pair {
        int x, y, cnt;
        
        public Pair(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
    
    public boolean inRange(int x, int y) {
        return 0 <= x && x < SIZE && 0 <= y && y < SIZE;
    }
    
    public boolean canGo(int x, int y) {
        if(!inRange(x, y)) return false;
        if(map[x][y] != 1 || visited[x][y]) return false;
        return true;
    }
    
    public void bfs(int startX, int startY, int itemX, int itemY) {
        visited[startX][startY] = true;
        q.add(new Pair(startX, startY, 0));
        
        while(!q.isEmpty()) {
            Pair cur = q.poll();
            
            if(cur.x == itemX && cur.y == itemY) {
                answer = cur.cnt/2;
                return;
            }
            
            for(int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if(canGo(nx, ny)) {
                    q.add(new Pair(nx, ny, cur.cnt + 1));
                    visited[nx][ny] = true;
                }
            }
        }
    }
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        
        int n = rectangle.length;
        // 도형 바깥쪽은 1, 안쪽은 2
        // map이 2이면 도달 불가능
        // map부분이 이상함. 다시 생각하기. 그림 그려야 할 듯?
        for(int i = 0; i < n; i++) {
            int x1 = rectangle[i][0] * 2;
            int y1 = rectangle[i][1] * 2;
            int x2 = rectangle[i][2] * 2;
            int y2 = rectangle[i][3] * 2;
            for(int p = x1; p <= x2; p++) {
                for(int q = y1; q <= y2; q++) {
                    if(p == x1 || p == x2 || q == y1 || q == y2) {
                        if(map[p][q] == 0) {
                            map[p][q] = 1;    
                        }
                    } else {
                        map[p][q] = 2;
                    }
                }
            }
        }
        
        bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
        
        return answer;
    }
}

코드 설명

• Pair 클래스
  • 좌표를 나타내는 x와 y를 저장하는 좌표와 현재 step의 값을 저장하는 클래스입니다.
  • BFS 탐색 시 현재 위치를 나타내기 위해 사용됩니다.

public boolean inRange(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

public boolean canGo(int x, int y) {
    if(!inRange(x, y)) return false;
    if(visited[x][y] || globalMaps[x][y] == 0) return false;
    return true;
}

• inRange 메소드
  다음 탐색해야하는 좌표가 배열 내부인지 확인하기 위한 메소드
• canGo 메소드
  다음 탐색해야하는 좌표로 이동이 가능한지 확인하기 위한 메소드(배열 내인지, 방문한 좌표인지, 다음 좌표가 벽인지)

public void bfs(int startX, int startY, int itemX, int itemY) {
    visited[startX][startY] = true;
    q.add(new Pair(startX, startY, 0));

    while(!q.isEmpty()) {
        Pair cur = q.poll();

        if(cur.x == itemX && cur.y == itemY) {
            answer = cur.cnt/2;
            return;
        }

        for(int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if(canGo(nx, ny)) {
                q.add(new Pair(nx, ny, cur.cnt + 1));
                visited[nx][ny] = true;
            }
        }
    }
}

• bfs 메소드
  • 큐에 현재 위치와 이동 횟수를 저장합니다.
  • 상하좌우 네 방향을 탐색하며 이동 가능(canGo)한 경우 큐에 추가합니다.
  • 목표 위치(itemX, itemY)에 도달하면 이동 횟수 / 2한 값을 저장합니다.

public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
    int n = rectangle.length;
    // 도형 바깥쪽은 1, 안쪽은 2
    // map이 2이면 도달 불가능
    // map부분이 이상함. 다시 생각하기. 그림 그려야 할 듯?
    for(int i = 0; i < n; i++) {
        int x1 = rectangle[i][0] * 2;
        int y1 = rectangle[i][1] * 2;
        int x2 = rectangle[i][2] * 2;
        int y2 = rectangle[i][3] * 2;
        for(int p = x1; p <= x2; p++) {
            for(int q = y1; q <= y2; q++) {
                if(p == x1 || p == x2 || q == y1 || q == y2) {
                    if(map[p][q] == 0) {
                        map[p][q] = 1;    
                    }
                } else {
                    map[p][q] = 2;
                }
            }
        }
    }

    bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);

    return answer;
}

• solution 메소드
  • 모든 사각형(rectangle)을 테두리(1)와 내부(2)로 분류하여 map에 저장합니다.
  • 좌표 확장
    • 좌표를 *2하여 지도 상에서 모든 이동을 정수 단위로 표현합니다.
  • BFS를 이용해 시작 위치에서 목표 위치까지 탐색합니다.
•  

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

dfs를 통해 모든 케이스를 돌면서 단어 변환이 되는지 체크하는 문제였습니다.

소스코드

import java.util.*;

class Solution {
    
    static boolean[] visited;
    static int answer = Integer.MAX_VALUE;
    
    // s1에서 s2로 가능한지.
    public boolean canChange(String s1, String s2) {
        int dif_cnt =0;

        for(int i = 0; i < s1.length(); i++){
          if(s1.charAt(i) != s2.charAt(i)){
            dif_cnt++;
          }
        }
        // 다른 문자가 1개일때
        if(dif_cnt == 1){
          return true;
        }
        // 다른문자가 한개가 아닐때
        return false;
    }
             
    public void dfs(String begin, String target, String[] words, int cnt) {
        if(begin.equals(target)) {
            answer = Math.min(answer, cnt);
            return;
        }
        
        for (int i = 0; i < words.length; i++) {
            if (visited[i]) {
                continue;
            }

            if(canChange(begin, words[i])) {
                visited[i] = true;
                dfs(words[i], target, words, cnt+1);
                visited[i] = false;
            }
        }
    }
      
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        
        dfs(begin, target, words, 0);
        
        if(answer == Integer.MAX_VALUE) {
            answer = 0;
        }
        
        return answer;
    }
}

코드 설명

• 전역변수
  • visited: 방문한 인덱스 확인
  • answer: target으로 변화 가능한 최솟값 저장.

// s1에서 s2로 가능한지.
public boolean canChange(String s1, String s2) {
    int dif_cnt =0;

    for(int i = 0; i < s1.length(); i++){
      if(s1.charAt(i) != s2.charAt(i)){
        dif_cnt++;
      }
    }
    // 다른 문자가 1개일때
    if(dif_cnt == 1){
      return true;
    }
    // 다른문자가 한개가 아닐때
    return false;
}

• canChange 메소드
  s1에서 s2로 이동이 가능한지(알파벳이 하나만 다른지) 확인하는 함수입니다.

public void dfs(String begin, String target, String[] words, int cnt) {
    if(begin.equals(target)) {
        answer = Math.min(answer, cnt);
        return;
    }

    for (int i = 0; i < words.length; i++) {
        if (visited[i]) {
            continue;
        }

        if(canChange(begin, words[i])) {
            visited[i] = true;
            dfs(words[i], target, words, cnt+1);
            visited[i] = false;
        }
    }
}

• dfs 메소드
  현재 값이 target과 같으면 answer를 업데이트 하고 종료합니다.
  • 방문한 인덱스면 반복을 계속하며, 단어 변환이 가능하면 업데이트합니다.
• answer가 Integer.MAX_VALUE면 0을 반환, 이외면 answer를 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

BFS를 활용한 문제였습니다. BFS/DFS 문제들은 중복 방문에 대한 처리를 확인해주셔야하며 OutOfRange가 나지 않기 위해
validation 체크를 진행해주셔야 합니다.

소스코드

import java.util.*;

class Solution {
    
    class Pair {
        int x, y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    int n, m;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    int[][] s;
    boolean[][] visited;
    int[][] globalMaps;
    Queue<Pair> q = new LinkedList<>();
    
    public void init() {
        s = new int[n][m];
        visited = new boolean[n][m];
        q.add(new Pair(0, 0));
        s[0][0] = 1;
        visited[0][0] = true;
    }
    
    public boolean inRange(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }
    
    public boolean canGo(int x, int y) {
        if(!inRange(x, y)) return false;
        if(visited[x][y] || globalMaps[x][y] == 0) return false;
        return true;
    }
    
    public void bfs() {
        while(!q.isEmpty()) {
            Pair cur = q.poll();
            for(int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if(canGo(nx, ny)) {
                    q.add(new Pair(nx, ny));
                    visited[nx][ny] = true;
                    s[nx][ny] = s[cur.x][cur.y] + 1;
                }
            }
        }
    }
    
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        globalMaps = new int[n][m];
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                globalMaps[i][j] = maps[i][j];
            }
        }
        
        init();
        bfs();
        
        if(s[n-1][m-1] == 0) {
            return -1;
        }
        return s[n-1][m-1];
    }
}

코드 설명

• 변수 설명
  • n: maps의 행
  • m: maps의 열
  • globalMaps: 다른 메소드에서 접근하기 위한 maps의 복사본
  • s: 각 위치까지의 이동 거리를 저장하는 2차원 배열입니다.
  • visited: i행 j열 방문했는지 확인하기위한 배열
  • q: BFS 탐색을 위한 큐로, 탐색해야 할 좌표를 저장합니다.

public void init() {
    s = new int[n][m];
    visited = new boolean[n][m];
    q.add(new Pair(0, 0));
    s[0][0] = 1;
    visited[0][0] = true;
}

public boolean inRange(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

public boolean canGo(int x, int y) {
    if(!inRange(x, y)) return false;
    if(visited[x][y] || globalMaps[x][y] == 0) return false;
    return true;
}

• init 메소드
  전역 변수 초기화 메소드
• inRange 메소드
  다음 탐색해야하는 좌표가 배열 내부인지 확인하기 위한 메소드
• canGo 메소드
  다음 탐색해야하는 좌표로 이동이 가능한지 확인하기 위한 메소드(배열 내인지, 방문한 좌표인지, 다음 좌표가 벽인지)

public void bfs() {
    while(!q.isEmpty()) {
        Pair cur = q.poll();
        for(int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if(canGo(nx, ny)) {
                q.add(new Pair(nx, ny));
                visited[nx][ny] = true;
                s[nx][ny] = s[cur.x][cur.y] + 1;
            }
        }
    }
}

• dx와 dy 테크닉을 통해 다음 탐색 좌표로 이동할 수 있으면 방문 처리 후 스텝을 1 증가시킵니다.

if (s[n-1][m-1] == 0) {
    return -1;
}
return s[n-1][m-1];

• s배열이 0이면 -1을 아니면 그 값을 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

연결되어 있는 노드를 DFS로 이동하면서 트리의 갯수를 찾는 문제입니다.

union-find로도 문제를 풀 수 있겠지만 DFS를 통해 문제를 해결했습니다. 

소스코드

import java.util.ArrayList;

class Solution {
    boolean[] visited;
    int answer = 0;
    
    public void dfs(int n, int start, int[][] computers) {
        visited[start] = true;
        for(int i = 0; i < n; i++) {
            if (i == start) continue;
            if (!visited[i] && computers[start][i] == 1) {
                dfs(n, i, computers);
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        visited = new boolean[n];
        for(int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(n, i, computers);
                answer++;
            }
        }
        
        return answer;
    }
}

코드 설명

public void dfs(int n, int start, int[][] computers) {
    visited[start] = true; // 현재 컴퓨터를 방문 처리
    for(int i = 0; i < n; i++) { // 모든 컴퓨터를 탐색
        if (i == start) continue; // 자기 자신과의 연결은 무시
        if (!visited[i] && computers[start][i] == 1) { // 방문하지 않았고 연결된 경우
            dfs(n, i, computers); // 재귀 호출로 탐색
        }
    }
}

• visited[start] = true;
  현재 컴퓨터는 방문 처리합니다
• for문
  자기 자신과의 연결은 무시한 후 방문하지 않았고 연결된 경우 재귀 호출로 탐색합니다.

public int solution(int n, int[][] computers) {
    visited = new boolean[n]; // 방문 여부를 초기화
    for(int i = 0; i < n; i++) { // 모든 컴퓨터를 순회
        if (!visited[i]) { // 방문하지 않은 컴퓨터를 발견하면
            dfs(n, i, computers); // 해당 컴퓨터에서 연결된 네트워크 탐색
            answer++; // 네트워크 개수 증가
        }
    }
    return answer;
}

• visited 배열을 초기화 한 후 방문하지 않은 네트워크 중 연결된 네트워크의 갯수를 for문을 통해 순회합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

DFS를 활용하여 재귀함수를 통해 타겟 넘버를 찾는 코드입니다. 익숙하면 금방 풀리겠지만, 저는 재귀와 같은 부분이 많이 헷갈려 조금 헤맸던 문제였습니다. 재귀함수를 통해 문제를 풀 때에는 종료 조건을 제일 중요하게 생각해야합니다.

소스코드

class Solution {
    int[] arr;
    int targetNumber, answer = 0;
    
    public void findTargetNum(int num, int cnt) {
        if (num == targetNumber && cnt == arr.length) {
            answer++;
            return;
        }
        if (cnt >= arr.length) return;
        
        findTargetNum(num - arr[cnt], cnt + 1);
        findTargetNum(num + arr[cnt], cnt + 1);
    }
    
    public int solution(int[] numbers, int target) {
        int n = numbers.length;
        arr = new int[n];
        targetNumber = target;
        
        for(int i = 0; i < n; i++) {
            arr[i] = numbers[i];
        }
        
        findTargetNum(-1 * arr[0], 1);
        findTargetNum(arr[0], 1);
        
        return answer;
    }
}

코드 설명

public void findTargetNum(int num, int cnt) {
    if (num == targetNumber && cnt == arr.length) {
        answer++;
        return;
    }
    if (cnt >= arr.length) return;

    findTargetNum(num - arr[cnt], cnt + 1);
    findTargetNum(num + arr[cnt], cnt + 1);
}

• num은 현재까지 계산된 합계이며, cnt는 현재 탐색중인 배열의 인덱스 입니다.
• 종료조건
  • num == targetNumber && cnt == arr.length:
    현재까지 계산된 값이 targetNumber와 같고, 배열의 모든 원소를 사용했다면 경우의 수를 1 증가시킵니다.
  • cnt >= arr.length
    배열의 끝까지 도달했지만 targetNumber에 도달하지 못하면 탐색을 종료합니다.
• 재귀 호출
  • findTargetNum(num - arr[cnt], cnt + 1):
    현재 숫자를 빼는 경우를 탐색합니다.
  • findTargetNum(num + arr[cnt], cnt + 1):
    현재 숫자를 더하는 경우를 탐색합니다.

public int solution(int[] numbers, int target) {
    int n = numbers.length;
    arr = new int[n];
    targetNumber = target;

    for(int i = 0; i < n; i++) {
        arr[i] = numbers[i];
    }

    findTargetNum(-1 * arr[0], 1);
    findTargetNum(arr[0], 1);

    return answer;
}

• 배열을 복사하고 타겟 넘버를 복사합니다. 전역변수로 사용해서 findTargetNum에서 사용하기 위함입니다.
• findTargetNum(-1 * arr[0], 1)
  첫 번째 숫자를 빼는 경우부터 시작합니다.
• findTargetNum(arr[0], 1)
  첫 번째 숫자를 더하는 경우부터 시작합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

원형으로 이루어진 집들에서 이웃집 체크를 할 때에 첫번째 집과 마지막 집을 체크하는 것이 문제였습니다. 이를 위해 동적 계획법을 두가지로 나누어 두 부분의 최댓 값중 더 큰 값을 반환하는 로직으로 문제를 해결하였습니다.

소스코드

class Solution {
    
    public int solution(int[] money) {
        int n = money.length;
        /* 
         * 첫번째 집을 포함하고 마지막 집을 빼는 경우
         * n까지 고려했을 때의 돈의 최댓값
         */ 
        int[] dp_includeFirst = new int[n]; 
        dp_includeFirst[0] = money[0];
        dp_includeFirst[1] = Math.max(money[1], money[0]);
        for(int i = 2; i < n-1; i++) {
            dp_includeFirst[i] = Math.max(money[i] + dp_includeFirst[i-2], dp_includeFirst[i-1]);
        }
        
        /* 
         * 첫번째 집을 제외하고 마지막 집을 선택하는 경우
         * n까지 고려했을 때의 돈의 최댓값
         */ 
        int[] dp_excludeFirst = new int[n]; 
        dp_excludeFirst[0] = 0;
        dp_excludeFirst[1] = money[1];
        for(int i = 2; i < n; i++) {
            dp_excludeFirst[i] = Math.max(money[i] + dp_excludeFirst[i-2], dp_excludeFirst[i-1]);
        }
        
        return Math.max(dp_excludeFirst[n-1], dp_includeFirst[n-2]);
    }
}

코드 설명

첫 번째 집을 포함하고 마지막 집은 제외.

• dp_includeFirst[i]: 0번째 집부터 i번째 집까지 고려했을 때, 훔칠 수 있는 최대 금액.
• 초기값:
  • 첫 번째 집(money[0])은 반드시 포함됨: dp_includeFirst[0] = money[0].
  • 두 번째 집은 첫 번째 집과 비교해 더 큰 금액 선택: dp_includeFirst[1] = Math.max(money[1], money[0]).
• for (int i = 2; i < n-1; i++) { dp_includeFirst[i] = Math.max(money[i] + dp_includeFirst[i-2], dp_includeFirst[i-1]); }
  • i번째 집을 포함하거나 포함하지 않는 경우 중 최대값 계산:
    • money[i] + dp_includeFirst[i-2]: 현재 집(i)을 포함하고, i-2번째 집까지의 최대값을 더함.
    • dp_includeFirst[i-1]: 현재 집을 포함하지 않고, i-1번째 집까지의 최대값.
  • 마지막 집(n-1)은 포함되지 않으므로 제외.

첫 번째 집을 제외하고 마지막 집을 포함.

• dp_excludeFirst[i]: 첫 번째 집을 제외하고, 1번째 집부터 i번째 집까지 고려했을 때의 최대 금액.
• 초기값:
  • 첫 번째 집은 제외되므로, dp_excludeFirst[0] = 0.
  • 두 번째 집은 money[1]으로 초기화: dp_excludeFirst[1] = money[1].
• for (int i = 2; i < n; i++) { dp_excludeFirst[i] = Math.max(money[i] + dp_excludeFirst[i-2], dp_excludeFirst[i-1]); }
  • 마지막 집(n-1)까지 포함.
• return Math.max(dp_excludeFirst[n-1], dp_includeFirst[n-2]);
  • 최대값 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

어렸을 때에 수학 문제를 풀 때에 가장자리에 1씩 두고 중간 값은 같은 열 위의 행과 같은 행 왼쪽 열의 합을 더해주는 방식을 사용했습니다.

소스코드

import java.util.*;

class Solution {
    private final int MOD = 1000000007;
    private final int DISABLE = -1;

    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n][m];
        for(int[] puddle: puddles) {
            dp[puddle[1]-1][puddle[0]-1] = DISABLE;
        }
        
        // init
        dp[0][0] = 1;
        for(int i = 1; i < m; i++) { // 가로
            if (dp[0][i] == DISABLE || dp[0][i-1] == DISABLE) {
                break;
            } else {
                dp[0][i] = 1;
            }
        }
        for(int i = 1; i < n; i++) { // 세로
            if (dp[i][0] == DISABLE || dp[i-1][0] == DISABLE) {
                break;
            } else {
                dp[i][0] = 1;
            }
        }
        
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(dp[i][j] == DISABLE) continue;
                
                if (dp[i-1][j] == DISABLE) {
                    dp[i][j] = dp[i][j-1];
                } else if (dp[i][j-1] == DISABLE) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = (dp[i-1][j] % MOD + dp[i][j-1] % MOD) % MOD;
                }
            }
        }
        
        return dp[n-1][m-1] % MOD;
    }
}

코드 설명

• int[][] dp = new int[n][m]; for(int[] puddle: puddles) { dp[puddle[1]-1][puddle[0]-1] = DISABLE; }
  
  • dp배열을 초기화합니다.
  • 웅덩이 위치에는 상수로 정의한 DISABLE로 설정합니다.
• 가장자리 초기화
  
  • 가로와 세로의 값을 초기화합니다.
  • 만약 웅덩이가 있다면 그 이후로는 처리를 하지 않습니다.

for(int i = 1; i < n; i++) {
    for(int j = 1; j < m; j++) {
        if(dp[i][j] == DISABLE) continue;
        
        if (dp[i-1][j] == DISABLE) {
            dp[i][j] = dp[i][j-1];
        } else if (dp[i][j-1] == DISABLE) {
            dp[i][j] = dp[i-1][j];
        } else {
            dp[i][j] = (dp[i-1][j] % MOD + dp[i][j-1] % MOD) % MOD;
        }
    }
}

• 현재 칸 (i, j)는 위 칸(dp[i-1][j])과 왼쪽 칸(dp[i][j-1])에서 올 수 있습니다.
• 웅덩이(DISABLE)가 있는 경우
  • 위 칸이 웅덩이면 왼쪽 경로만 고려합니다.
  • 왼쪽 칸이 웅덩이면 위쪽 경로만 고려합니다.
• dp[i][j]=(dp[i-1][j]%MOD+dp[i][j-1]%MOD)%MOD
  • 위와 왼쪽 모두 웅덩이가 아니라면 두 경로의 합을 계산합니다.
• return dp[n-1][m-1] % MOD;
  • 결과를 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

삼각형 형태로 있는 숫자를 이차원 배열로 생각하여 문제를 풀었습니다. 현재 행의 i-1에 j열 또는 j-1의 합으로 문제를 풀었습니다.

여기에서 ArrayIndexOutOfBoundsException이 나오지 않게 체크를 해줍니다.

소스코드

int solution(int[][] triangle) {
        int len = triangle.length;
        int[][] ans = new int[len][len];
        for(int i = 0; i < len; i++) {
            for(int j = 0; j <= i; j++) {
                ans[i][j] = triangle[i][j];
            }
        }

        // init
        for(int i = 1; i < len; i++) {
            ans[i][0] = ans[i - 1][0] + triangle[i][0];
            ans[i][i] = ans[i - 1][i - 1] + triangle[i][i];
        }

        for(int i = 2; i < len; i++) {
            for(int j = 1; j < i; j++) {
                ans[i][j] = Math.max(ans[i-1][j-1], ans[i-1][j]) + triangle[i][j];
            }
        }

        int answer = Integer.MIN_VALUE;
        for(int i = 0; i < len; i++) {
            answer = Math.max(answer, ans[len-1][i]);
        }

        return answer;
    }
}

코드 설명

• 초기화
  
  • len: 삼각형의 높이.
  • ans: 각 위치까지의 최대 합을 저장하는 2차원 DP 배열.
  • 삼각형의 값을 그대로 ans 배열에 복사합니다.

for (int i = 1; i < len; i++) {
    ans[i][0] = ans[i - 1][0] + triangle[i][0]; // 삼각형 맨 왼쪽 경로
    ans[i][i] = ans[i - 1][i - 1] + triangle[i][i]; // 삼각형 맨 오른쪽 경로
}

삼각형의 왼쪽 끝 경로와 오른쪽 끝 경로는 고정된 값만 참조하므로 초기화합니다.

• 왼쪽 끝 경로는 위쪽 요소에서만 내려옵니다.
• 오른쪽 끝 경로도 마찬가지입니다.

for (int i = 2; i < len; i++) {
    for (int j = 1; j < i; j++) {
        ans[i][j] = Math.max(ans[i - 1][j - 1], ans[i - 1][j]) + triangle[i][j];
    }
}

• 중간 경로 계산
  
  • 위치 ans[i][j]는 위에서 내려올 수 있는 두 가지 경로 중 더 큰 값을 선택합니다:
    • ans[i-1][j-1]: 왼쪽 대각선 위에서 내려오는 경로.
    • ans[i-1][j]: 바로 위에서 내려오는 경로.
  • 이 중 더 큰 값을 선택해 현재 위치의 값을 갱신합니다.
• 마지막 행에서 가장 큰 값을 조회 후 반환합니다.