[BOJ] - 최단경로 / 1753번 (Java)

[BOJ] - 최단경로 / 1753번 (Java) [BOJ] - 최단경로 / 1753번 (Java) 1. 문제 접근 시작 정점에서 모든 정점까지의 최단거리를 구하면 되는 문제다. 간선의 가중치를 의미하는 w값이 10이하의 "자연수"이므로, 음의 가중치를 갖지 않는다. 따라서, 다익스트라(Dijkstra)알고리즘을 사용하여 구현하면 된다. 현재 위치한 노드에서 방문할 수 있는 노드를 선별하는 것이 핵심이다. Node adNode = adList[currNodeNum]; while (adNode != null) { // 방문한 노드는 PASS, 도달하는 비용이 업데이트 되지 않으면 PASS if (!isVisited[adNode.nodeNum] && currCost + adNode.weight < dist[..

• format_list_bulleted 알고리즘
• · 2024. 2. 28.
• textsms

[BOJ] - 아기 상어 / 16236번 (Java)

[BOJ] - 아기 상어 / 16236번 (Java) [BOJ] - 아기 상어 / 16236번 (Java) 1. 문제 접근 문제를 요약하면, 아기 상어가 먹을 수 있는 먹이를 모두 먹는데 이동한 거리는 얼마인지 구하는 문제다. 단 상어의 이동과 먹을 수 있는 경우에 조건이 몇가지 존재한다. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수..

• format_list_bulleted 알고리즘
• · 2024. 2. 27.
• textsms

[BOJ] - 외판원 순회 2 / 10971번 (Java)

[BOJ] - 외판원 순회 2 / 10971번 (Java) [BOJ] - 외판원 순회 2 / 10971번 (Java) 1. 문제 접근 기존의 외판원 순회 문제에서 최종 목적지에서 출발지로 다시 돌아와야하는 변형된 외판원 순회 문제다. 또한, 각 도시마다 경로가 있을 수도 있고, 없을 수도 있다. 도시의 개수(N)이 최대 10개 밖에 되지 않으므로, 모든 도시를 줄세우는 방식의 순열을 사용하여 완전 탐색을 할 수 있다. 하지만 이전 도시와 다음 도시 간에 간선이 있는지 없는지에 따라 백트래킹을 진행하였다. int beforeNode = selectList[selectIdx - 1]; int currNode = elementList[idx]; // 경로가 없는 경우 pruning if (adMatrix[be..

• format_list_bulleted 알고리즘
• · 2024. 2. 26.
• textsms

[BOJ] - 연구소 / 14502번 (Java)

[BOJ] - 연구소 / 14502번 (Java) [BOJ] - 연구소 / 14502번 (Java) 1. 문제 접근 N x N 크기의 연구소에 2이상 10이하 개수를 갖는 바이러스가 있을 때, 총 3개의 벽을 빈 공간에 세워 얻을 수 있는 안전영역의 최대 크기를 구하면 된다. 먼저 입력(N)의 크기가 최대 8로 크지 않다. 완전 탐색을 통해 나이브하게 경우의 수를 살펴 보면 64 Combination 3 (벽을 선택하는 경우의 수) x 바이러스를 퍼트리는 시간(= rowMax || tempCol >= colMax) continue; // 방문 검증 if (isVisited[tempRow][tempCol]) continue; // 벽 검증 if (map[tempRow][tempCol] == 1) conti..

• format_list_bulleted 알고리즘
• · 2024. 2. 26.
• textsms

[BOJ] - 거짓말 / 1043번 (Java)

[BOJ] - 거짓말 / 1043번 (Java) [BOJ] - 거짓말 / 1043번 (Java) 1. 문제 접근 사실을 알고 있는 사람이 존재 할 때, 거짓말을 칠 수 있는 파티의 개수를 구하면 되는 문제다. 사실을 알고있는 사람들과, 그러한 사람들과 동일한 파티 멤버들을 하나의 집합으로 관리하면 된다. Union Find 알고리즘을 사용하여 진실을 알고있는 사람들과 그와 관련된 사라들을 관리하면 쉽게 풀 수 있다. 단, 진실을 알고있는 사람의 수가 0명이라면바로 파티의 수가 거짓말을 칠 수 있는 파티 수의 최대이므로 총 파티의 수를 출력하고 종료한다. if(memberNumberKnowTruth == 0) { // 진실을 아는 사람이 없는 경우 System.out.println(partyNumber);..

• format_list_bulleted 알고리즘
• · 2024. 2. 25.
• textsms

[BOJ] - 임계경로 / 1948번 (Java)

[BOJ] - 임계경로 / 1948번 (Java) [BOJ] - 임계경로 / 1948번 (Java) 1. 문제 접근 사이클이 없는 유향 그래프가 주어 질 때, 가장 마지막에 도착하는 시간과 그러한 사람들이 거쳐온 경로의 개수를 구하면 된다. "즉 전체 공정 중 가장 시간이 많이 걸리는 경로이다. 각 작업의 공정을 그래프 형태로 나타냈을 때 임계 경로는 시작점에서 종료점에 이르는 가장 긴 경로가 된다." 출처 - [TTA정보통신 용어사전] "사이클이 없는 유향그래프"로 부터 위상 정렬을 사용하여 최장 거리를 수할 수 있음을 알 수 있다. 문제는 최장거리는 쉽게 구할 수 있지만, 임계경로의 개수를 어떻게 구해야하는 것에 대한 발상이 어려웠다. 정방향(출발지 -> 도착지)의 위상정렬을 구해가며 모든 경로를 노..

• format_list_bulleted 알고리즘
• · 2024. 2. 25.
• textsms