코딩테스트/백준_Java
-
Q. 3055 자바 : 탈출코딩테스트/백준_Java 2023. 4. 9. 13:27
Q. 3055 자바 : 탈출 문제 : boj.kr/3055 골드 4 난이도의 문제이다. 격자형 그래프가 주어지고, 비어있는 곳은 '.', 물이 차있는 지역은 '*', 돌은 'X', 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 주어질 때 S가 D로 갈 수 있는 최단경로를 계산하는 문제이다. 주의해야 할 점은 물이 차있는 지역인 *는 비어있는 곳 '.'로 확산되고, 물이 차있는 지역은 고슴도치가 갈 수 없다는 점 이다. 어떻게 풀지 고민을 해봤더니, 먼저 물이 차있는 곳에 대해 BFS를 하고 이후에 고슴도치가 BFS를 하면 풀 수 있을 것 같아 이렇게 풀었다. 1. 물이 차있는 곳을 큐에 넣는다. 2. 고슴도치의 위치는 저장했다가, 물이 차있는 곳이 모두 큐에 들어가면 이후에 큐에 넣는다. 3. 탐색을..
-
Q. 1697 자바 : 숨바꼭질코딩테스트/백준_Java 2023. 4. 8. 13:16
Q. 1697 자바 : 숨바꼭질 문제 : boj.kr/1697 실버 1 난이도의 문제이다. 두 점 N, K가 주어지고, N이 이동할 수 있는 방식은 총 3개이며 각각 1초가 소요된다면(N + 1, N - 1, N * 2)N이 K로 갈 수 있는 가장 빠른 시간을 구하는 문제이다. 만약 그래프 탐색 관련 문제를 풀고 있지 않았다면처음 이 문제를 봤을 때 그래프 탐색 문제라고 생각하지 못했을 것 같다.고민해보니 세가지 이동방식에 대한 BFS를 이용하면 풀 수 있을 것 같아 이 방식을 이용해서 풀었다. 1. 정점 N에서 이동 가능한 세 가지 방식에 따른 좌표를 큐에 넣는다.2. 만약 방문했다면 재방문하지 않는다.(가장 먼저 방문한 경우가 가장 빠른 경우이므로 재방문했다면 더 빨라질 수는 없다.) 시간복잡도를 계..
-
Q. 2178 자바 : 미로 탐색코딩테스트/백준_Java 2023. 4. 7. 09:06
Q. 2178 자바 : 미로 탐색 문제 : boj.kr/2178 실버 1 난이도의 문제이다. 격자형 그래프의 크기 N, M과 그래프가 주어졌을 때 1,1부터 N,M까지 갈 수 있는 최소 이동 횟수를 출력하는 문제이다. 주의해야 할 점은 시작점인 1, 1과 도착점인 N, M도 이동 횟수에 포함된다는 점 이다. 최악의 경우는 아래와 같은 경우이며 111111111 100000000 111111111 100000000 111111111 100000000 111111111 이 경우 시간복잡도는 약 O(NM)이다. 이 문제의 경우 N과 M의 최대값이 100이므로 시간초과는 걱정하지 않아도 된다. 또한 도착위치로 이동할 수 없는 경우는 주어지지 않는다고 했으므로 고려하지 않아도 되고, 이동 가능한 칸과 이동이 불가..
-
Q. 11725 자바 : 트리의 부모 찾기코딩테스트/백준_Java 2023. 4. 6. 09:48
Q. 11725 자바 : 트리의 부모 찾기 문제 : boj.kr/11725 실버 2 난이도의 문제이다. 정점의 개수와 간선이 주어졌을 때(방향성x) 만약 1번 정점이 루트라면 2번 정점부터 부모 노드의 번호를 출력하는 문제이다. 처음 이 문제를 봤을 때는 좀 막막했다. 만약 그래프 탐색 문제인줄 모르고 봤다면 문제를 푸는데 시간이 더 오래 걸렸을 것 같다. 고민을 좀 해보니, 간선이 다 주어지므로 모든 간선을 입력받은 뒤에루트가 1이므로 1부터 탐색을 해 가면서 방문 여부를 확인하면 될 것 같다는 생각이 들었다. 그래서 아래와 같은 방식으로 풀었다.1. 입력된 모든 간선은 양방향 그래프이므로, 모두 연결한다.2. 1번 정점부터 탐색을 하면서, 어떤 정점에서 호출 됬는지(부모)를 저장한다. 시간 복잡도는 ..
-
Q. 11403 자바 : 경로 찾기코딩테스트/백준_Java 2023. 4. 5. 09:31
Q. 11403 자바 : 경로 찾기 문제 : boj.kr/11403 실버 1 난이도의 문제이다. 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로 존재 여부를 구하라는 내용이다. 그래프 탐색 강의를 듣고 예제 문제를 푸는 도중이었는데 이 문제는 List를 그래프 탐색이라고 되어 있어서 List를 사용해서 풀었지만, 만약 이를 몰랐다면 입력이 격자형 그래프로 주어져서 격자형 그래프로 풀었을 것 같다. 문제를 이해하는데 시간이 좀 걸렸다.. 입력이 아래와 같이 주어졌을 때 3 0 1 0 0 0 1 1 0 0 출력이 아래와 같다. 1 1 1 1 1 1 1 1 1 즉 정점이 0, 1, 2가 있다면 입력을 간선으로 바꾸면 0 -> 1, 1 -> 2, 2 -> 0..
-
Q. 2606 바이러스코딩테스트/백준_Java 2023. 4. 4. 09:04
Q. 2606 바이러스 문제 : boj.kr/2606 실버 3 난이도의 문제이다. 컴퓨터의 수와 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어지고 이후에 연결된 컴퓨터 쌍이 주어진다 이 때 1번 컴퓨터가 바이러스에 걸렸다면, 1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수를 계산하는 문제이다. 이를 그래프로 설명하자면 양방향 그래프가 주어지고 정점과 간선의 수 그리고 간선이 주어진다. 이 때 1번 정점에 연결된 다른 정점의 수를 계산하는 문제이다. 그래프와 연결된 간선을 List로 구현한 뒤 dfs, bfs 두 방식으로 풀었다 List를 이용한 그래프 탐색의 경우 정점을 V, 간선을 E라고 하면 시간복잡도가 O(V + E)이고 문제 조건에서 정점이 최대 100개이므로 이 경우 간선이 ..
-
Q. 14502 연구소코딩테스트/백준_Java 2023. 4. 3. 12:20
Q. 14502 연구소 문제 : boj.kr/14502 골드 4 난이도의 문제이다. 바이러스(2) 벽(1) 빈 공간(0)을 의미하는 격자형 그래프가 주어지고, 바이러스는 빈 공간이 있으면 확산된다는 조건이 있다. 이 때 벽을 세 개 세워서 바이러스의 확산을 최대한 막는 방법을 물어보는 문제이다. 처음 문제를 봤을 때 든 생각은 벽을 세울 수 있는 모든 경우의 수를 dfs로 구현한 뒤 벽을 3개 만들었을 경우, 바이러스를 확산시켜 빈 공간의 수를 계산하는 방식을 떠올렸다. 근데 막상 구현을 하다 보니 너무 복잡해지는 것 같아 생각을 바꿨다. 아래와 같은 방식으로 구현을 했다. 1. 빈 공간(0)을 리스트에 모두 저장한다. 2. 벽을 최대 3개 세울 수 있으므로 3중for문을 이용해 벽을 세울 수 있는 모든..
-
Q. 3184 자바 : 양코딩테스트/백준_Java 2023. 4. 2. 01:07
Q. 3184 자바 : 양 문제 : boj.kr/3184 실버 1 난이도의 문제이다. 격자형 그래프에 양, 늑대, 울타리가 주어지고, 울타리 내에 양과 늑대의 수를 비교해서, 양이 더 많을경우 늑대를 없애고 늑대와 양의 수가 같거나 늑대가 많을 경우 양을 없앤다. 이후 모든 울타리에 생존한 양과 늑대에 수를 출력하는 문제이다. 생각해야 되는 입력값이 빈 필드, 양, 늑대, 울타리이고, 이걸 어떻게 탐색을 하면 될까 고민해서 아래와 같은 방식으로 풀었다. 1. 처음 시작할 때는 양이나 늑대일 경우 탐색을 시작한다. (모든 탐색 여부는 visit[][] 배열에 표시) 2. 이후 다른 영역을 탐색할 때는 울타리가 아닌 경우 무조건 탐색을 한다. 3. 위 탐색이 한 번 끝나면 양과 늑대의 수를 비교해 조건에 따..