전체 글
BOJ 11403 경로 찾기 [Java]
BOJ 11403 경로 찾기 1. 문제 링크 https://www.acmicpc.net/problem/11403 2. 문제 해설 플로이드 알고리즘을 이용하면 쉽게 풀 수 있다. 정점의 최대 갯수가 100개이므로 최대 연산 수는 1000000으로 넉넉하게 통과한다. 입력으로 arr배열을 받고 1이 아니면 (Integer.MAX_VALUE - 1) / 2로 초기화해준다. Integer.MAX_VALUE로 초기화할 시 31번째 줄 코드에서 오버플로우가 발생할 수 있다는 점을 주의하자. 그 후 플로이드 과정을 거치고 arr[i][j] 값이 아직 (Integer.MAX_VALUE - 1) / 2 인 곳은 갈 수 있는 경로가 없다는 의미이다. 그러므로 그런 위치는 0, 아닌 곳은 1을 출력해주면 쉽게 해결할 수 있..
2021 카카오 채용연계형 인턴십 Lv2 거리두기 확인하기 [Java]
2021 카카오 채용연계형 인턴십 Lv2 거리두기 확인하기 1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/81302 2. 문제 해설 카카오 2021 채용연계형 인턴십 코딩테스트의 2번 문제이다. 맨해튼 거리가 2이하면 안된다는 의미는 bfs를 동서남북으로 돌았을 때 깊이 2 이하로는 참가자가 있으면 안된다는 의미이다. 각 대기실을 돌면서 참가자를 만나면 bfs를 돌아 거리두기 확인 여부를 검사하는 방식으로 풀고자 했다. 일단 큰 틀을 먼저 잡기 위해 int 배열을 반환하는 solution 메서드를 먼저 구현했다. 5가지 대기실의 거리두기를 지켰는지 여부를 담을 answer 배열을 만들어준다. 그리고 3중 for문을 돌아야하는데, i는 대기실의 ..
BOJ 15683 감시 [Java]
BOJ 15683 감시 1. 문제 링크 https://www.acmicpc.net/problem/15683 2. 문제 해설 백트래킹을 이용하여 cctv를 다 돌면서 cctv들의 방향에 따른 모든 조합의 경우를 다 보는 방식의 풀이를 생각했다. 방향을 어떻게 표현할 것인지가 문제였는데, 그냥 단순히 동쪽, 북쪽, 서쪽, 남쪽을 0, 1, 2, 3으로 대응시키기로 하였다. 우선 주어지는 입력에서 cctv의 위치와 타입을 저장하기위해 CCTV 클래스를 만들고 CCTV 배열을 만들어 cctv를 모두 담아주었다. 그리고 백트래킹을 이용하여 방향에 따른 모든 경우의 수를 다 살펴봐야하는데, cctv의 타입에 따라 방향의 갯수가 달라진다. cctv 타입에 대응되는 방향의 갯수를 담는 cctv_dir 배열을 만들어주었..
BOJ 1753 최단경로 [Java]
BOJ 1753 최단경로 1. 문제 링크 https://www.acmicpc.net/problem/1753 2. 문제 해설 다익스트라 알고리즘을 이용하는 기본 문제이다. 다익스트라 알고리즘 구현을 연습하기에 좋았다. 코드 구현에 대한 설명은 아래 다익스트라 알고리즘에 대해 써놓은 글을 참고해보자. [최단 거리 알고리즘 - 다익스트라 [Java]] 3. 코드 보기 import java.io.*; import java.util.*; public class Main { static class Node implements Comparable { int vertex; int distance; public Node(int vertex, int distance) { this.vertex = vertex; this.d..
최단 거리 알고리즘 - 다익스트라 [Java]
목차 1. 서론 2. 작동원리 3. 구현 1. 서론 다익스트라 알고리즘은 한 정점에서 다른 정점들까지의 최단 거리와 경로를 구하는 알고리즘이다. 단, 간선의 거리 정보는 항상 0 이상이어야 한다. 2. 작동원리 1. 방문하지 않은 정점 중 가장 시작점으로부터 거리가 짧은 정점으로 이동한다. 이 때, 해당 정점까지의 최단 거리는 확정된다. 2. 현재 정점과 인접한 모든 정점들 중 방문하지 않은 정점들을 돌면서 거리를 갱신시켜준다. 즉, 현재 정점까지의 최단 거리를 A, 현재 정점과 인접한 정점 V를 잇는 간선의 거리를 B, 현재까지 구한 V까지의 최단거리를 C라고 했을 때, A+B < C 이면 V까지의 최단 거리를 A+B로 갱신해준다는 의미이다. 위 과정을 아래에서 그림으로 한번 살펴보자. 아래 그림은 영..