다익스트라 > 4485번 / 그리디 > 1339번

4485번

 

이전 다익스트라 문제들은 인접 리스트를 사용하여 풀었지만 해당 문제는 인접 행렬을 사용하였다

// 인접 행렬과 최단 경로

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class baekjoon4485 {

    static int n; // 동굴의 크기
    static int[][] graph; // 동굴 내 도둑 루피 정보를 담은 이차원 배열
    static boolean[][] visited; // 방문 여부 확인
    static int[] dx = {-1, 1, 0, 0}; // 좌우 이동
    static int[] dy = {0, 0, -1, 1}; // 상하 이동
    static int[][] result; // 최단 경로를 담을 이차원 배열
    static int i = 0;

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            n = Integer.parseInt(br.readLine());
            if (n == 0) break;
            graph = new int[n][n];
            visited = new boolean[n][n];
            result = new int[n][n];
            for (int i = 0; i < n; i++) {
                String[] str = br.readLine().split(" ");
                for (int j = 0; j < n; j++) {
                    graph[i][j] = Integer.parseInt(str[j]);
                }
            }
            sb.append("Problem "+(++i)+": "+다익스트라(0, 0)+"\n");
        }
        System.out.println(sb);
    }

    public static int 다익스트라(int x, int y) {
        PriorityQueue<Treasure> queue = new PriorityQueue<>();
        for(int i = 0; i<n; i++) {
            Arrays.fill(result[i], Integer.MAX_VALUE); // 이차원 배열의 초기값 설정
        }
        queue.offer(new Treasure(x, y, graph[x][y]));
        result[x][y] = graph[x][y];
        while (!queue.isEmpty()) {
            Treasure tr = queue.poll();
            if (!visited[tr.x][tr.y]) {
                visited[tr.x][tr.y] = true;
                for (int i = 0; i < dx.length; i++) {
                    int xx = tr.x + dx[i];
                    int yy = tr.y + dy[i];
                    if (check(xx, yy) && result[xx][yy] > result[tr.x][tr.y] + graph[xx][yy]) {
                        result[xx][yy] = result[tr.x][tr.y] + graph[xx][yy];
                        queue.offer(new Treasure(xx, yy, result[xx][yy]));
                    }
                }
            }
        }
        return result[n-1][n-1];
    }

    public static boolean check(int x, int y) {
        if (x < 0 || y < 0 || x >= n || y >= n || visited[x][y]) { // 동굴을 벗어나거나 방문한 경우 false 반환
            return false;
        }
        return true;
    }
}

class Treasure implements Comparable<Treasure> {
    int x;
    int y;
    int rupee;

    Treasure(int x, int y, int rupee) {
        this.x = x;
        this.y = y;
        this.rupee = rupee;
    }

    @Override
    public int compareTo(Treasure t) {
        return this.rupee - t.rupee; // 도둑 루피 오름차순 정렬
    }
}

 

1339번

 

// AABC와 DDDD가 있다고 하자
// AABC = 1000A + 100A + 10B + 1C
// DDDD = 1000D + 100D + 10D + 1D
// 알파벳 배열 A 인덱스에 1000, B 인덱스에 10, C 인덱스에 1, D 인덱스에 1000+100+10+1의 값이 들어간다
// alphabet[0] = 1100, alphabet[1] = 10, alphabet[3] = 1, alphabet[4] = 1111
// 해당 배열을 내림차순으로 정렬,  1111*9 + 1000*8 + 10*7 + 1*6 = 18875

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;

public class baekjoon {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        Integer [] alphabet = new Integer [26]; // 알파벳 배열 ([A: 0]~[Z: 26]까지)
        Arrays.fill(alphabet, 0);  // int 배열의 초기값은 0이지만 객체 배열의 초기값은 null > 따로 0으로 초기화 필요
        for(int i = 0; i<num; i++) {
            String str = br.readLine();
            int multiple = 1;
            for(int j = str.length()-1; j>=0; j--) {
                alphabet[str.charAt(j)-'A'] += multiple;
                multiple *= 10;
            }
        }
        Arrays.sort(alphabet, Collections.reverseOrder()); // 내림차순 정렬
        int n = 9;
        int answer = 0;
        for(int i = 0; i<alphabet.length; i++) {
            if(alphabet[i] == 0) break; // 이미 정렬한 상태이므로 더 이상 반복문 실행할 필요 없음
            answer += alphabet[i] * n;
            n--;
        }
        System.out.println(answer);
    }
}