알고리즘

[백준] 10282: 해킹 / JAVA

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 설명 기본적인 다익스트라 문제입니다. 시간이 더 짧게 소모되는 경로로 우선순위큐에서 빼지만 한 번 체크한 지점보다 더 짧은 경로가 나올 수 있으므로 방문배열을 사용하지 않았습니다. ex) 3번 컴퓨터가 감염되는 시간은 8초가아니라 6초입니다. 1 -> 3 = 8초 1 -> 2 -> 3 = 6초 2 1 2 3 1 8 3 2 4 풀이

[백준] 6087번: 레이저 통신 / JAVA

https://www.acmicpc.net/problem/6087 설명 방향 변경을 최소로 목표 지점에 도착해야 하는 문제입니다. 방향을 바꿔 움직일때마다 거울을 설치하고 매번 거울을 최소로 설치해서 움직일 수 있는 경로를 가져옵니다. (우선순위 큐) 방향을 enum 클래스로 만들어 보았습니다. 방향을 바꿨다면 비용이 1 증가하게 됩니다. 풀이

[백준] 5972: 택배 배송 / JAVA

https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 설명 기본 다익스트라 문제입니다. 목표 지점까지의 최소 비용을 구하면 됩니다. 우선순위 큐와 방문 배열을 활용하여 풀이하였습니다. 풀이

[백준] 1753: 최단경로 / JAVA

https://www.acmicpc.net/problem/1753 설명 기본적인 다익스트라 문제다. 코드를 보고 이해하기 어렵다면 다익스트라 개념을 먼저 익혀야한다. [백준] 1753: 최단경로 / JAVA 풀이

[백준] 14496번: 그대, 그머가 되어 / JAVA

https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 설명 입력 받은 좌표를 양뱡향 이동이 가능한 2차원 배열로 만든다. 우선순위 큐를 이용하여 최단 거리를 구한다. 풀이

[백준] 4485: 녹색 옷 입은 애가 젤다지? / JAVA

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 설명 출발 지점으로부터 도착지점까지 최소 비용을 구하는 문제입니다. 한 칸씩 이동하는 BFS 개념과 비용이 적은 곳부터 이동하게 우선순위를 사용하여 풀이가 가능합니다. 풀이

[백준] 1504: 특정한 최단 경로 / JAVA

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 설명 다익스트라 유형에서 조금 변형이 일어난 문제입니다. 반드시 거쳐야 할 지점이 존재합니다. 반드시 방문해야 되니 특정 지점으로만 이동해보면서 도착지까지 거리를 구하면 됩니다. 2가지의 경로가 존재합니다. 1 -> v1 -> v2 -> N 1 -> v2 -> v1 -> N 두 가지의 경로중 더 적은 비용으로 도착하는 방법이 최단 거리가 됩니다. 이번엔..

[백준] 1916번: 최소 비용 구하기 / JAVA

1916번 최소 비용 구하기 https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 설명 이번 문제는 한 지점까지의 최소비용을 구하면 됩니다. 다익스트라의 개념을 이해하고있으면 쉽게 풀 수 있는 문제입니다. 방문 배열을 만들어 풀이도 가능합니다. 풀이

[백준] 2564: 경비원 / JAVA

https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 설명 (0, 0)을 기준으로 1차원 배열로 만들어 각 위치의 최단거리를 구할 수 있습니다. 위 그림을 1차원 배열로 만들어줍니다. 1차원 배열로 만들면 위와 같은 배열이 만들어집니다. 그다음 X 좌표에서 타깃을 하나씩 좌, 우로 거리를 재면서 짧은 경로를 구하면 됩니다. 저는 타깃에 번호를 매겨서 해당 번호를 추적하였습니다. 풀이

[백준] 1584번: 게임 / JAVA

https://www.acmicpc.net/problem/1584 1584번: 게임 첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 www.acmicpc.net 설명 움직일 때마다 생명이 적게 소모되는 곳을 먼저 탐색하면 되므로 우선순위 큐를 이용한 BFS 탐색을 하면 됩니다. 풀이