https://www.acmicpc.net/problem/1717 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;//https://www.acmicpc.net/problem/1717public class 유니온파인드1_집합의표현 { static int[] parent; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

https://www.acmicpc.net/problem/1753 풀이 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.PriorityQueue;import java.util.StringTokenizer;//https://www.acmicpc.net/problem/1753public class Main { private static int E; private static int V; private static int K; private static ArrayList[] AL; private static int[]..

https://www.acmicpc.net/problem/11779 23% 시간초과로 어리둥절했던 문제이다.분명 다익스트라로 잘 구현했는데 시간초과가 발생했다. 문제는 아래 핵심이라고 주석메모를 해놓은 부분이다. 다익스트라를 구현 할 때 가중치가 작은 순으로 PQ에 담기는데,큐에서 꺼낸 노드의 누적 비용(cur.w)이 해당 노드의 dist[cur.v]와 다를 수 있는 경우가 발생한다는 것이다.언제? 간선의 수(m)가 많아질수록, 즉 복잡한 그래프일수록 발생할 가능성이 높아진다. 간선의 수가 적을 때만 테스트 해보니 간과했던 부분이었다. 더보기왜 이런 상황이 발생하는지 설명하겠습니다:PriorityQueue 특성: 다익스트라 알고리즘에서 우선순위 큐는 가장 짧은 거리를 가진 노드를 먼저 꺼냅니다. 하지만 ..

https://www.acmicpc.net/problem/21608 PQ를 활용한 구현문제이다.1시간 정도 소요되었고 디버깅 한번으로 통과한 문제. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.PriorityQueue;import java.util.StringTokenizer;public class b21608_상어초등학교 { private static class Student implements Comparable { int y; int x; int like; int blank; public Stude..

https://www.acmicpc.net/problem/19238 정확히 어떤 테스트케이스인지는 모르겠으나 1%와 6%에서 너무 괴롭혔다.  1. 문제 조건에 성립하기 위해선 direction 순서도 상/좌/우/하 로 설정해주는 것이 좋다.2. 맵을 그릴 때 0이 빈칸, 1이 벽으로 주어지기 때문에, 승객 및 도착지 번호는 2부터 시작하도록 한다.3. 승객을 찾는 findGuest() 에서 PQ를 사용하되, 주의할 점이 있다.(이부분에서 6%의 벽을 넘었다..)- while(큐가 빌때까지) 4방향을 돌면서 승객을 발견하는 경우는 PQ 모두 담은 뒤- PQ의 첫번째 요소를 리턴하는 방식으로 구현을 해준다.4. PQ에서 얻어낸 승객 정보를 바탕으로 도착지를 찾고, count를 해준다. 풀이코드import ..

구현 + 백트래킹 문제인데 구현하느라 엄청 애를 먹었다.. 문제 풀이하면서 슈도코드 작성한 걸 보면1. 물고기 이동- 1~16순으로 이동 . 이동 가능: 빈칸 & 다른물고기 . 이동 불가능: 상어 & 경로밖   + 반시계 회전: 나머지 연산 이용 2. 상어이동 - 여러칸 이동가능, 따라서 반복문 안에서 최대 3번 DFS  3. 1,2 반복 후 max 출력 풀이코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int max = -1; static int[] dy = {-1, -..