54번 게임 개발
내가 떠올린 풀이 해설
각 건물을 노드라고 생각하면 그래프 형태에서 노드 순서를 정렬하는 알고리즘인 위상 정렬을 사용하는 문제이다. 건물 수가 최대 500, 시간 복잡도가 2초이므로 시간제한 부담은 거의 없다. 입력을 바탕으로 자료구조를 초기화한다 인접 리스트로 그래프를 표현할 때는 인접 노드, 건물 번호를 Node로 선언하여 연결한다. 진입 차수 배열은 [0, 1, 2, 1], 정답 배열은 모두 0으로 초기화한다. 위상 정렬을 실행하면서 각 건물을 짓는데 걸리는 최대 시간을 업데이트합니다. 업데이트 방법은 Math.max(현재 건물에 저장된 최대 시간, 이전 건물에 저장된 최대 시간 + 현재 건물의 생산 시간)이다. 정답 배열에 자기 건물을 짓는 데 걸리는 시간을 더한 후 정답 배열을 차례대로 출력한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1516 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
int[] indegree = new int[n + 1];
int[] selfBuild = new int[n + 1];
for(int i = 0; i <= n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
selfBuild[i] = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
while(true) {
if(r == -1) {
break;
}
list.get(r).add(i);
indegree[i]++;
}
}
Queue<Integer> que = new LinkedList<>();
for(int i = 1; i <= n; i++) {
if(indegree[i] == 0) {
que.offer(i);
}
}
int[] result = new int[n + 1];
while(!que.isEmpty()) {
int now = que.poll();
for(int i : list.get(now)) {
indegree[i]--;
result[i] = Math.max(result[now], result[now] + selfBuild[now]);
if(indegree[i] == 0) {
que.offer(i);
}
}
}
for(int i = 1; i <= n; i++) {
System.out.println(result[i] + selfBuild[i]);
}
}
}
56번 최단경로
내가 떠올린 풀이 해설
시작점과 다른 노드와 관련된 최단 거리를 구하는 문제이다. 다익스트라 알고리즘의 가장 기본적인 형태를 구현할 수 있는지를 묻는 문제이다. 인접 리스트에 노드를 저장하고 거리 배열을 초기화한다. 거리 배열은 0으로 초기화한다. 최초 시작점을 큐에 삽입하고, 다음 과정에 따라 다익스트라 알고리즘을 수행한다. 마지막으로 완성된 거리 배열의 값을 출력한다.
다익스트라 수행 과정
1. 거리 배열에서 아직 방문하지 않은 노드 중 현재 값이 가장 작은 노드를 선택한다.
2. 해당 노드와 연결된 노드들의 최단 거릿값을 다음 공식을 이용해 업데이트한다.
- Min(선택 노드의 거리 배열의 값 + 에지의 가중치, 연결 노드의 거리 배열의 값이 업데이트된 경우 연결 노드를 큐에 삽입)
3. 큐가 빌 때까지 반복한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1753 {
static int n,m,k;
static boolean[] visit;
static int[] distance;
static ArrayList<Edge>[] list;
static PriorityQueue<Edge> que = new PriorityQueue<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(br.readLine());
distance = new int[n + 1];
list = new ArrayList[n + 1];
visit = new boolean[n + 1];
for(int i = 1; i <= n; i++) {
list[i] = new ArrayList<Edge>();
}
for(int i = 1; i <= n; i++) {
distance[i] = Integer.MAX_VALUE;
}
for(int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
list[s].add(new Edge(e, v));
}
que.add(new Edge(k, 0));
distance[k] = 0;
while(!que.isEmpty()) {
Edge current = que.poll();
int c_v = current.vertex;
if(visit[c_v]) {
continue;
}
visit[c_v] = true;
for(int i = 0; i < list[c_v].size(); i++) {
Edge tmp = list[c_v].get(i);
int next = tmp.vertex;
int value = tmp.value;
if(distance[next] > distance[c_v] + value) {
distance[next] = value + distance[c_v];
que.add(new Edge(next, distance[next]));
}
}
}
for(int i = 1; i <= m; i++) {
if(visit[i]) {
System.out.println(distance[i]);
}
else {
System.out.println("INF");
}
}
}
}
class Edge implements Comparable<Edge>{
int vertex, value;
Edge(int vertex, int value) {
this.vertex = vertex;
this.value = value;
}
@Override
public int compareTo(Edge o) {
if(this.value > o.value) {
return 1;
}
else {
return -1;
}
}
}오늘의 회고
오늘은 위상 정렬과 다익스트라 개념 공부와 다익스트라 기본 문제를 풀었습니다. 기본 문제인데 풀기 힘들었습니다. 또한 Do it! 알고리즘 코딩 테스트 (26번 ~ 28번)까지 복습을 진행하였습니다. 처음 알고리즘을 공부할 때는 재미도 없고 알고리즘이 필요가 있을까라는 생각을 했었는데 알고리즘을 공부하면서 점점 재미가 있고 모르는 문제를 고민하면서 해결 능력을 길러나가는 점에서 많은 도움이 될 것이라고 생각합니다. 매일 똑같은 말이지만 오늘보다 나은 내일을 위해 다짐을 한다고 생각해 주시면 감사하겠습니다. 성장하는 저를 위해 꾸준히 천천히 한 발 한 발 나아가겠습니다.
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
| Do it! 알고리즘 코딩 테스트 (61번) (0) | 2022.06.16 |
|---|---|
| Do it! 알고리즘 코딩 테스트 (57번 ~ 59번) (0) | 2022.06.15 |
| Do it! 알고리즘 코딩 테스트 (52번 ~ 53번) (0) | 2022.06.13 |
| Do it! 알고리즘 코딩 테스트 (51번) (0) | 2022.06.10 |
| Do it! 알고리즘 코딩 테스트 (50번) (0) | 2022.06.09 |
