자바로 코테 준비하기😈 - 스택, 우선순위 큐, 그래프

1️⃣ 스택 Stack

Stack<Integer> stack = new Stack<>();

stack.push(1);  // 값 추가
stack.pop();   // 값 삭제
stack.clear();  // 값 전체삭제
stack.size();  // 크기 반환
stack.empty();  // 비어있으면 true, 아니면 false
stack.contains(1);  // 1을 포함하고 있으면 true, 아니면 false
stack.peek();  // Stack top 출력 (제거 X), 비어있으면 null 반환

2️⃣ 큐 Queue

Queue<Integer> q = new LinkedList<>();

q.add(1);  // 값 추가
q.offer(2);  // 값 추가
q.poll();  // 첫 번째 값 반환, 비어있으면 null 반환
q.remove();  // 첫 번째 값 제거
q.clear();  // 값 모두 삭제
q.peek();  // 첫 번째 값 출력 (제거 X)
q.isEmpty();  // 큐가 비었으면 true

3️⃣ 우선순위 큐 PriorityQueue

디폴트는 최소힙

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.add(1);  // 값 추가
pq.offer(1)  // 값 추가
pq.poll();  // 첫 번째 값 반환, 비어있으면 null 반환
pq.remove();  // 첫 번째 값 제거
pq.size();  // 크기 반환
pq.clear();  // 값 모두 삭제
pq.peek();  // 첫 번째 값 출력 (제거 X)

4️⃣ 그래프

깊이 우선 탐색 DFS

class Solution {
    int answer = 0;  // 전역변수 선언 
    
    public void dfs(int idx, int result, int target, int[] numbers) {
        if (idx == numbers.length) {
            if (result == target) 
                answer += 1;
        }
        else {
            dfs(idx+1, result+numbers[idx], target, numbers);
            dfs(idx+1, result-numbers[idx], target, numbers);
        }
    }
    
    public int solution(int[] numbers, int target) {
        dfs(0, 0, target, numbers);
        return answer;
    }
}

너비 우선 탐색 BFS

1차원 코드

import java.util.*;

class Solution {
    static boolean visited[];
    int answer = 0;
    
    public void bfs(int[][] computers, int start) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = true;
        
        while (!q.isEmpty()) {
            int now = q.poll();
            
            for (int i = 0; i < computers.length; i++) {
                if (computers[now][i] == 1 && !visited[i]) {
                    q.add(i);
                    visited[i] = true;
                }
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        visited = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                bfs(computers, i);
                answer += 1;
            }
        }
        
        return answer;
    }
}

​
2차원 코드

class Solution {
    int[] dy = {-1, 1, 0, 0};
    int[] dx = {0, 0, -1, 1};
    
    public void bfs(int[][] maps, int[][] dist) {
        dist[0][0] = 1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        
        while (!q.isEmpty()) {
            int[] cur = q.remove();
            int y = cur[0];
            int x = cur[1];
            
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                
                if (nx < 0 || ny < 0 || nx >= maps[0].length || ny >= maps.length)
                    continue;
                
                if (dist[ny][nx] == 0 && maps[ny][nx] == 1) {
                    dist[ny][nx] = dist[y][x] + 1;
                    q.add(new int[]{ny, nx});
                }
            }
        }
    }
    
    public int solution(int[][] maps) {
        int answer = 0;
        int[][] dist = new int[maps.length][maps[0].length];  // false로 초기화 
        
        bfs(maps, dist);
        answer = dist[maps.length-1][maps[0].length-1];
        
        if (answer == 0)
            answer = -1;
        
        return answer;
    }
}