Computer Science Knowledge Storage

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

포인트

잃어버린 결과표에서 순위를 알 수 있는 선수의 수를 구하는 문제였습니다.
순위를 안다는 것은 누군가에게 지고 이겼는지에 대한 모든 결과를 알고 있으면 되므로 wins 배열과 loses 배열을 통해 확인합니다.

소스코드

import java.util.*;

class Solution {
    List<List<Integer>> wins = new ArrayList<>();
    List<List<Integer>> loses = new ArrayList<>();
    
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        for(int i = 0; i <= n; i++) {
            wins.add(new ArrayList<>());
            loses.add(new ArrayList<>());
        }
        
        for(int[] result: results) {
            int win = result[0];
            int lose = result[1];
            wins.get(win).add(lose);
            loses.get(lose).add(win);
        }
        
        for(int i = 1; i <= n; i++) {
            boolean[] visited = new boolean[n + 1];
            Queue<Integer> q = new LinkedList<>();
            
            visited[i] = true;
            q.add(i);
            while(!q.isEmpty()) {
                int win = q.poll();
                for(int lose: wins.get(win)) {
                    if (visited[lose]) continue;
                    visited[lose] = true;
                    q.add(lose);
                }
            }
            
            q.add(i);
            while(!q.isEmpty()) {
                int lose = q.poll();
                for(int win: loses.get(lose)) {
                    if (visited[win]) continue;
                    visited[win] = true;
                    q.add(win);
                }
            }
            
            boolean flag = true;
            for(int j = 1; j <= n; j++) {
                if(!visited[j]) {
                    flag = false;
                }
            }
            if (flag) {
                answer++;
            }
        }
        
        return answer;
    }
}

코드 설명

• 변수 설명
  • List<List<Integer>> wins = new ArrayList<>();
    List<List<Integer>> loses = new ArrayList<>();
    src가 이긴 desc가 진 배열이 wins 배열, src가 진 desc가 이긴 배열이 loses 배열입니다.

for(int i = 0; i <= n; i++) {
    wins.add(new ArrayList<>());
    loses.add(new ArrayList<>());
}

for(int[] result: results) {
    int win = result[0];
    int lose = result[1];
    wins.get(win).add(lose);
    loses.get(lose).add(win);
}

• wins 배열과 loses 배열을 초기화합니다.

for(int i = 1; i <= n; i++) {
    boolean[] visited = new boolean[n + 1];
    Queue<Integer> q = new LinkedList<>();

    visited[i] = true;
    q.add(i);
    while(!q.isEmpty()) {
        int win = q.poll();
        for(int lose: wins.get(win)) {
            if (visited[lose]) continue;
            visited[lose] = true;
            q.add(lose);
        }
    }

    q.add(i);
    while(!q.isEmpty()) {
        int lose = q.poll();
        for(int win: loses.get(lose)) {
            if (visited[win]) continue;
            visited[win] = true;
            q.add(win);
        }
    }

• 첫번째 while문을 통해 i가 이긴 선수들과 이긴 선수들의 결과표를 통해 인덱스를 방문합니다.
• 두번째 while문을 통해 i가 진 선수들과 진 선수들의 결과표를 통해 인덱스를 방문합니다.

boolean flag = true;
    for(int j = 1; j <= n; j++) {
        if(!visited[j]) {
            flag = false;
        }
    }
    if (flag) {
        answer++;
    }
}

return answer;

• 모든 배열을 방문하였다면 순위를 알 수 있는 것이므로 answer를 증가하고 반복문 종료시 answer를 반환합니다.
•  

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

포인트

bfs 탐색을 통해 1번 노드에서 가장 먼 노드를 찾는 문제였습니다. 저는 visited 배열과 step 배열을 통해서 문제를 풀었습니다.

소스코드

import java.util.*;

class Solution {
    boolean[] visited;
    int[] step;
    List<List<Integer>> graph = new ArrayList<>();
    Queue<Integer> q = new LinkedList<>();
    
    public void bfs() {
        while(!q.isEmpty()) {
            int src = q.poll();
            for(int desc: graph.get(src)) {
                if (!visited[desc]) {
                    visited[desc] = true;
                    step[desc] = step[src] + 1;
                    q.add(desc);
                }
            }
        }
    }
    
    public void init(int n) {
        visited = new boolean[n + 1];
        step = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        q.add(1);
        visited[1] = true;
        step[1] = 1;
    }
    
    public int solution(int n, int[][] edge) {
        int answer = 1;
        
        init(n);
        
        for(int[] vertex: edge) {
            int src = vertex[0];
            int desc = vertex[1];
            graph.get(src).add(desc);
            graph.get(desc).add(src);
        }
        
        bfs();
        
        Arrays.sort(step);
        int max = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            if (max < step[i]) {
                answer = 1;
                max = Math.max(max, step[i]);
            } else if (max == step[i]) {
                answer++;
            }
        }
        
        return answer;
    }
}

코드 설명

• 변수 설명
  
  • boolean[] visited
    해당 인덱스의 노드를 방문했는지 확인하는 배열입니다.
  • int[] step
    해당 인덱스의 노드의 그래프의 깊이 입니다.
  • List<List<Integer>> graph = new ArrayList<>()
    src와 desc로 설정하여 graph를 설정합니다.
  • Queue<Integer> q = new LinkedList<>()
    bfs 를 위한 Queue를 선언합니다.
• bfs 메소드
  일반 bfs 메소드입니다.
  • src와 desc를 선언하여 방문하지 않은 desc면 q에 넣고 step도 초기화합니다.
• init 메소드
  변수들을 초기화하는 메소드입니다.

Arrays.sort(step);
int max = Integer.MIN_VALUE;
for(int i = 1; i <= n; i++) {
    if (max < step[i]) {
        answer = 1;
        max = Math.max(max, step[i]);
    } else if (max == step[i]) {
        answer++;
    }
}

return answer;

• 몇번 인덱스를 찾는 문제가 아니라 가장 먼 노드의 갯수를 구하는 문제이므로 Array를 정렬합니다.
• step이 가장 큰 노드를 찾으면 answer를 초기화 합니다.
• max와 step[i]가 같으면 answer을 1 증가합니다.
• 반복문 종료 후 answer를 반환합니다.

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

포인트

이 문제는 이분 탐색을 어떤 값으로 하느냐가 포인트였던 것 같습니다. 저는 바위 간의 거리의 최솟값을 기준으로 이분탐색을 진행하였습니다. 해당 바위 사이의 거리가 최솟값보다 크다면 삭제하고, 삭제한 값이 n보다 더 많으면 범위를 재탐색하는 로직으로 설계하였습니다.

하지만 해당 문제에서 제거한 바위의 갯수랑 n과 같을때로 설정하면 문제가 틀리고 제거한 바위가 n보다 작거나 같을때로 하면 정답이 되었습니다. 문제의 설명이 빠진 것인지 싶은데 혹시 해당 이유를 아시는 분 있으면 댓글달아주시면 감사드립니다😁

소스코드

import java.util.Arrays;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        Arrays.sort(rocks);
        
        int left = 1;
        int right = distance;
        
        // 바위의 거리의 최솟값을 기준으로 이분탐색
        while(left <= right) {
            int mid = (left + right) / 2;
            int deleteRocks = 0;
            int prevRock = 0;
            
            for(int rock: rocks) {
                if (Math.abs(rock - prevRock) < mid) {
                    deleteRocks++;
                } else {
                    prevRock = rock;
                }
            }
            
            if (distance - prevRock < mid) {
                deleteRocks++;
            }
            
            if (deleteRocks > n) {
                right = mid - 1;
            } else if (deleteRocks <= n) {
                left = mid + 1;
                answer = mid;
            }
        }
        
        return answer;
    }
}

코드 설명

• 변수 초기화
  • rocks: 바위 위치들을 정렬하여 바위들 사이의 거리를 쉽게 계산할 수 있도록 합니다
  • left: 최소 거리의 시작 값은 1로 설정합니다.
  • right: 최대로 가능한 거리 값은 전체 거리인 distance입니다.
• 이분탐색
  
  • mid: 현재 탐색 중인 거리 값입니다. 이 값은 최소 거리로 유지하면서 바위들을 제거할 수 있는지 확인하려는 값입니다.
  • deleteRocks: 제거된 바위의 갯수입니다.
  • prevRock: 이전 바위의 인덱스입니다. 처음에는 0으로 설정합니다.(초기값)
• 바위들 사이의 간격 체크
  
  • Math.abs(rock - prevRock) < mid: 현재 바위와 직전 바위 사이의 거리가 mid보다 작으면, 이 바위는 제거해야 하므로 deleteRocks를 증가시킵니다.
  • 그렇지 않으면, prevRock을 현재 바위로 업데이트하여 다음 바위와의 거리를 비교할 준비를 합니다.
• if (distance - prevRock < mid) { deleteRocks++; }
  마지막 바위와 거리 체크
• 범위설정
  • deleteRocks > n: 바위를 너무 많이 제거한 경우, mid값을 줄여야 하므로 right = mid - 1으로 범위를 좁힙니다.
  • deleteRocks <= n: 바위 제거 개수가 n개 이하인 경우, mid 값은 유효하므로 left = mid + 1로 범위를 확장하고, answer를 mid로 업데이트하여 더 큰 거리 값도 탐색할 수 있도록 합니다.

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

포인트

이분탐색을 이용하여 심사가 끝나는 시간을 기준으로 처리 가능한 총 인원을 계산하여 n보다 클 때에 값을 갱신하는
lowerbound(특정 조건을 만족하는 값 중에서 최솟값)를 사용했습니다. 

소스코드

import java.util.*;

class Solution {

    public long solution(int n, int[] times) {
        Arrays.sort(times);
        long answer = 0;
        long left = 1;
        long right = (long)times[times.length-1] * n; // 60
        
        while (left <= right) {
            long mid = (left + right) / 2; // 중간 시간
            long peopleProcessed = 0;

            // mid 시간 동안 처리 가능한 총 인원 계산
            for (int time : times) {
                peopleProcessed += mid / time;
                if (peopleProcessed >= n) break; // n명을 초과하면 더 계산할 필요 없음
            }

            if (peopleProcessed >= n) {
                answer = mid; // 더 작은 시간을 탐색
                right = mid - 1;
            } else {
                left = mid + 1; // 시간을 더 늘림
            }
        }

        return answer;
    }
}

코드 설명

• 변수 초기화
  • times: 각 심사대의 심사 시간이 들어있는 배열. 이 배열은 오름차순으로 정렬됩니다.
  • left: 가능한 시간의 최솟값 1입니다.
  • right: 최악의 경우 가장 느린 심사관이 n명을 모두 처리하는 시간(times[times.length-1] * n) 입니다.
• 이분탐색
  • mid: 현재 탐색 중인 시간입니다.
  • peopleProcessed: mid 시간 동안 각 심사관이 처리할 수 있는 총 인원 수를 계산합니다.
• mid 시간 동안 처리 가능한 인원 계산
  • mid / time: 각 심사관이 mid 시간 동안 처리 가능한 사람 수.
  • 총 처리 인원(peopleProcessed)이 n명을 넘으면 반복문을 종료합니다.
• 조건에 따라 탐색 범위 조정
  
  • peopleProcessed >= n: mid 시간이 충분히 길어 n명을 처리할 수 있는 경우, 더 작은 시간에서 조건을 만족하는지 확인합니다.
  • peopleProcessed < n: mid 시간이 부족하므로 시간을 늘려야 합니다.

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

포인트

해당 문제는 결합법칙을 무시한 채 최대 값을 구하기 위한 문제입니다. - 연산에서는 왼쪽 값은 최댓값, 오른쪽 값은 최솟값이 되어야 최대값이 되고, + 연산에서는 두 값 모두 최대 값이 되어야 합니다. 이를 통해 dpMax 배열과 dpMin 배열을 통해 문제를 풀었습니다.

소스코드

class Solution {
        public int solution(String[] arr) {
            int n = arr.length / 2 + 1; // 숫자의 개수
            int[][] dpMax = new int[n][n];
            int[][] dpMin = new int[n][n];

            // 숫자 초기화
            for (int i = 0; i < n; i++) {
                dpMax[i][i] = Integer.parseInt(arr[i * 2]);
                dpMin[i][i] = Integer.parseInt(arr[i * 2]);
            }

            // 구간 길이
            for (int len = 1; len < n; len++) {
                for (int i = 0; i < n - len; i++) {
                    int j = i + len;
                    dpMax[i][j] = Integer.MIN_VALUE;
                    dpMin[i][j] = Integer.MAX_VALUE;

                    // i부터 j까지 연산자에 대한 분할 계산
                    for (int k = i; k < j; k++) {
                        String operator = arr[k * 2 + 1];
                        int maxLeft = dpMax[i][k];
                        int minLeft = dpMin[i][k];
                        int maxRight = dpMax[k + 1][j];
                        int minRight = dpMin[k + 1][j];

                        if (operator.equals("+")) {
                            dpMax[i][j] = Math.max(dpMax[i][j], maxLeft + maxRight);
                            dpMin[i][j] = Math.min(dpMin[i][j], minLeft + minRight);
                        } else if (operator.equals("-")) {
                            dpMax[i][j] = Math.max(dpMax[i][j], maxLeft - minRight);
                            dpMin[i][j] = Math.min(dpMin[i][j], minLeft - maxRight);
                        }
                    }
                }
            }

            return dpMax[0][n - 1]; // 전체 구간의 최댓값 반환
        }
    }

코드 설명

• int n = arr.length / 2 + 1; // 숫자의 개수 int[][] dpMax = new int[n][n]; int[][] dpMin = new int[n][n];
  • n: 숫자의 개수. 연산자는 숫자보다 항상 하나 적으므로, 전체 배열 길이의 절반(arr.length / 2)에 1을 더해 계산합니다.
  • dpMax[i][j]: i번째 숫자부터 j번째 숫자까지 가능한 최대값을 저장합니다.
  • dpMin[i][j]: i번째 숫자부터 j번째 숫자까지 가능한 최소값을 저장합니다.
• for (int i = 0; i < n; i++) { dpMax[i][i] = Integer.parseInt(arr[i * 2]); dpMin[i][i] = Integer.parseInt(arr[i * 2]); }
  
  • 각 숫자는 연산 없이 자기 자신이므로, dpMax[i][i]와 dpMin[i][i]를 해당 숫자로 초기화합니다.

for (int len = 1; len < n; len++) {
    for (int i = 0; i < n - len; i++) {
        int j = i + len;
        dpMax[i][j] = Integer.MIN_VALUE;
        dpMin[i][j] = Integer.MAX_VALUE;

• len: 현재 계산하려는 구간의 길이. 길이가 1부터 시작하여, 점차 늘어나며 모든 가능한 구간을 탐색합니다.
• i: 구간의 시작점.
• j: 구간의 끝점. 구간 길이가 len이므로, j = i + len으로 계산.

for (int k = i; k < j; k++) {
    String operator = arr[k * 2 + 1];
    int maxLeft = dpMax[i][k];
    int minLeft = dpMin[i][k];
    int maxRight = dpMax[k + 1][j];
    int minRight = dpMin[k + 1][j];

• k: 구간을 분할하는 기준점.
  • arr[k * 2 + 1]에서 연산자(+, -)를 가져옵니다.
  • k를 기준으로 왼쪽(i에서 k)과 오른쪽(k+1에서 j)의 최대/최소값을 가져옵니다.
    • maxLeft, minLeft: 왼쪽 구간 최대/최소값.
    • maxRight, minRight: 오른쪽 구간 최대/최소값.

if (operator.equals("+")) {
    dpMax[i][j] = Math.max(dpMax[i][j], maxLeft + maxRight);
    dpMin[i][j] = Math.min(dpMin[i][j], minLeft + minRight);
} else if (operator.equals("-")) {
    dpMax[i][j] = Math.max(dpMax[i][j], maxLeft - minRight);
    dpMin[i][j] = Math.min(dpMin[i][j], minLeft - maxRight);
}

• 연산자에 따라 결과를 계산
  • + 연산: 양쪽 구간의 최대/최소값을 더합니다.
  • - 연산: 왼쪽 최대값에서 오른쪽 최소값을 빼거나, 왼쪽 최소값에서 오른쪽 최대값을 뺍니다.
• 계산 결과를 갱신하며, dpMax[i][j]는 가능한 최대값, dpMin[i][j]는 가능한 최소값을 유지합니다.
• return dpMax[0][n - 1];
  • dpMax[0][n-1]: 입력 배열 전체(0번째 숫자부터 마지막 숫자까지)의 가능한 최대값을 반환합니다.

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

포인트

모든 항공권을 사용해 가능한 여행 경로를 찾고, 사전순으로 가장 앞선 경로를 반환합니다.

소스코드

import java.util.*;

class Solution {
    int n;
    boolean[] visited;
    ArrayList<String> arr = new ArrayList<>();
    
    public void dfs(int cnt, String start, String path, String[][] tickets) {
        if(cnt == n) {
            arr.add(path);
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if (!visited[i] && tickets[i][0].equals(start)) {
                visited[i] = true;
                dfs(cnt+1, tickets[i][1], path + " " + tickets[i][1], tickets);
                visited[i] = false;
            }
        }
    }
    
    public String[] solution(String[][] tickets) {
        n = tickets.length;
        visited = new boolean[n+1];
        
        dfs(0, "ICN", "ICN", tickets);
        
        Collections.sort(arr);

        return arr.get(0).split(" ");
    }
}

코드 설명

• 전역변수 초기화
  • int n;
    항공권의 개수입니다.
  • boolean[] visited;
    항공권이 이미 사용되었는지 여부를 기록하는 배열입니다.
  • ArrayList<String> arr = new ArrayList<>();
    가능한 모든 경로를 저장하는 리스트입니다.

public void dfs(int cnt, String start, String path, String[][] tickets) {
    if(cnt == n) {
        arr.add(path);
        return;
    }

    for(int i = 0; i < n; i++) {
        if (!visited[i] && tickets[i][0].equals(start)) {
            visited[i] = true;
            dfs(cnt+1, tickets[i][1], path + " " + tickets[i][1], tickets);
            visited[i] = false;
        }
    }
}

• dfs 메소드
  • cnt == n이면 모든 항공권을 사용한 경로가 완성된 상태입니다.
  • 현재 위치 start와 일치하는 출발지를 가진 항공권을 찾습니다. 아직 사용되지 않은 항공권(!visited[i])만 선택합니다.
  • 선택한 항공권을 사용(visited[i] = true)하고, 목적지(tickets[i][1])로 이동합니다.
  • 재귀 호출이 끝난 후, 현재 항공권 사용 상태를 복구(visited[i] = false)하여 다른 경로를 탐색할 수 있도록 합니다.

public String[] solution(String[][] tickets) {
    n = tickets.length;
    visited = new boolean[n+1];

    dfs(0, "ICN", "ICN", tickets);

    Collections.sort(arr);

    return arr.get(0).split(" ");
}

• solution 메소드
  • 탐색을 시작하기 위해 dfs(0, "ICN", "ICN", tickets)를 호출합니다.
  • Collections.sort(arr)로 모든 경로를 사전순으로 정렬합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
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를 반환합니다.