Computer Science Knowledge Storage

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

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