Hailey

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net | 문제 해결방법 ⭐Idea : 크루스칼 알고리즘 가장 기본적인 크루스칼 알고리즘 문제 [JAVA] 해설 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.ut..

https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net | 문제 해결방법 ⭐Idea : 크루스칼 알고리즘 ( '가장 적은 간선으로 모든 노드를 연결하는 방법' 을 구하기 ) 크루스칼 알고리즘은 모든 간선을 연결하는 최소 비용을 구할 때 사용한다. 각 간선의 크기가 주어진 경우라면, 간선의 크기로 오름차순 정렬을 해준 후 정렬된 순서대로 간선을 연결한다. ✔ 하지만 이 문제는 간선의 크기가 없어서 간선의 크기는 고려..

| 문제 해결방법 BFS (+ 사방탐색 가능 여부 체크) 이 문제는 단순한 BFS문제이다. BFS로 탐색하면서 주어진 시간만큼동안 이동할 수 있는 위치의 개수를 출력해주면 된다. 단, 터널의 모양에 따라 다음 위치로의 이동 여부가 결정된다. 터널은 1번부터 7번까지 다 다른 모양을 가지고 있다. 상, 우, 하, 좌 순서로 터널 모양에 따라 이동 가능한 방향은 true, 이동이 불가한 방향은 false로 저장한 deltas 배열을 사용하였다. (터널이 1~7번까지 있기 때문에 0번째 열은 자리를 채워주기 위해 임의로 준 값- 사용하지 X) static boolean[][] deltas = { { false, false, false, false }, { true, true, true, true }, // 1..

최근에 백준에서 동일한 문제를 푼 기억이 있어서 금방 풀었던 문제이다. 백준 4485번 녹색 옷 입은 애가 젤다지? 링크 : https://www.acmicpc.net/problem/4485 | 문제 해결방법 다익스트라 + 우선순위 큐 ★다익스트라 알고리즘과 우선순위 큐(Priority Queue)를 함께 사용하면 효율이 극대화된다. [JAVA] 해설 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; class node implements Comparable{ int r, c, cost; public node(int r, int..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net | 문제 해결방법 이 문제는 제목에서 대놓고 힌트를 주고 있다. 플로이드-워셜 알고리즘으로 문제를 풀면 된다. 기본적인 플로이드-워셜 문제와 거의 동일하다. 한 가지 다른 점은 예제를 한 번 손으로 적으면서 돌려보면 알 수 있는데, 같은 간선에 비용만 다른 경우가 존재한다. 이 경우 우리가 하려고 하는 값은 최소 비용이기 때문에 작은 비용을 선택해주면 된다. 그리고 내가 두 번이나 틀렸던 이유로 ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net | 문제 해결방법 관련 알고리즘 : bfs + 인접행렬 1. 입력받은 네트워크 쌍을 이용해 인접행렬을 초기화 한다. 2. (1,1) 부터 시작하여 네트워크로 연결되어 있는 컴퓨터를 모두 탐색한다.( bfs + visited[] ) 3. visited[] (방문한 컴퓨터는 true가 됨) 배열에서 true의 개수를 반환(1번 컴퓨터는 counting하지 않음) [JAVA] 해설 코드 import java..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net | 문제 해결방법 개인적으로 굉장히 쉬운 문제였다. 단지별로 단지 번호, count만 잘 처리해주면 인접리스트 + bfs로 쉽게 해결 관련 알고리즘 : 인접리스트 + bfs [JAVA] 해설 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arra..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net | 문제 해결방법 관련 알고리즘 : bfs (dfs로 시간초과가 난 후 방법을 bfs로 변경) 인접행렬 * O(V^2) 인접리스트 * O(V+E) 처음에 인접행렬 + dfs로 풀 방법은 시간초과 이후 인접리스트 + bfs로 방법을 바꾸어 풀어서 해결했다. [JAVA] 해설 코드 1. 인접행렬 + dfs (시간초과) package graph; import java.io.BufferedReade..