HwangHub

🤔 Intuition BFS를 이용한 완탐으로 보였다. 귀신이 남우를 따라잡는 여부를 어떻게 알 수 있나 기준을 잡는 게 중요했는데, 귀신이 남우보다 먼저 목적지에 갈 수 있는 경우에는 무조건 귀신이 남우를 따라잡을 수 있는 것으로 봤다. 여기서 고민을 했던 부분은 최악의 경우 10^6 개의 귀신을 가질 텐데, 이들이 모두 BFS를 돌면 시간을 쉬이 초과할 것이다. 따라서 탐색을 할 귀신을 선정하는 게 중요한데, 나는 도착지와 맨해튼 거리가 가장 가까운 귀신만 검사해줬다. 어차피 가장 가까운 귀신의 이동 거리만 필요하기 때문이다. (솔직히 처음에 제출할 때에는, "에이 그래도 이게 뻑이 안나도록 문제를 줬을거야 누가봐도 BFS 문제인데?" 라는 아주아주 안일한 생각을 했다. 결론은, 문제에서 단순 완탐이..

🤔 Intuition 시뮬레이션 문제인 것은 확실하나, 탐색을 어떻게 할지 고민하였다. 우선되는 먹이의 조건이 (1) 거리가 가까울 것 (2) row가 작을 것 (3) column이 작을 것 이었으므로 델타탐색을 "상 좌 우 하" 로 하면서 가장 먼저 나오는 먹이를 낼름 먹어버리면 될 것으로 봤다. 하지만 위는 틀렸다. 위의 경우에는 항상 거리값이 가장 가까운 먹이를 찾을 수 있지만, 바로 만난 먹이가 가장 위에 있고, 가장 왼쪽에 있다는 것을 보장할 수 없다. 아래 예시를 보면 이해가 가능하다. private static int[] dy = {-1, 0, 0, 1}; private static int[] dx = {0, -1, 1, 0}; . . 1 . . . 2 x 3 . 4 x C x 6 . 5 x..

해석 이 문제는 인접 리스트를 이용하여 relation group의 개수를 묻는 문제이다. 따라서 그래프 탐색을 통해 연관 노드를 한번에 방문하는 방식으로 로직을 전개하면 마을의 개수를 구할 수 있다. 보통 격자 상에서의 그래프 알고리즘이 아닌, 이 문제와 같이 인접 행렬 또는 인접 리스트를 활용하는 그래프 알고리즘의 시간복잡도는 인접 행렬과 리스트 각각 O(v^2), O(v + e)이다. 이는 아래 구현된 로직에서도 확인할 수 있다. 노드의 개수가 최대 100개라고 주어져 있으므로, 인접 행렬이든 리스트든 관련 없이 문제를 풀 순 있었을 것이다. 간선의 개수는 n(n-1)/2개라고 되어있으므로 인접 행렬로 구현하였다. 풀이 DFS package ssafy.사전학습.그래프; import java.io.B..

유형 파악 이 문제는 2차원 배열 상의 출발지에서 목적지까지 이동시간의 최소를 구하는 문제이면서, 이동간 시간 가중치가 동일하기 때문에 전형적인 BFS 문제라고 이해할 수 있다. 아울러, 몇 개의 점을 선택하여 제거하는 경우를 세야 하므로 이 부분은 백트래킹 로직을 활용하여 풀어내 주었다. 제출 코드 구성했던 로직의 특징은, 여러 경우에서 도착지에 도달하는 시간이 도출될텐데, 그 경우 중 가장 빠른 경우에서의 시간을 구하는 것을 우선순위 큐를 활용하여 도출해줬다는 것과, 제거하려는 벽을 중복으로 선택하지 않기 위해 selected[][] 라는 배열을 운영한 것이다. 개인적으로 헤맨 부분은, 백트래킹을 통해 제거할 벽을 모두 선택했을 때 bfs를 수행하기 위해 관련 변수들을 초기화해줘야 한다는 것이다. 이..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 가중치가 일정한 상황에서 각 귤에 도달되는 시간을 숫자로 표현하는 문제이므로 BFS 문제임을 알 수 있다. 상한 귤들은 시작점이 되고, 인접한 귤로만 이동하면서 time을 1초씩 추가하면 된다. 이를 기록하는 배열은 별도로 선언한다. 그 외에 -1, -2 와 같은 결과 출력 양식을 맞춰주기 위해서는 출력 단계에서 조건문으로 처리해주면 깔끔하다. 문제 풀이 public class 상한_귤 { private static class Pair { private int x, y; private Pair..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 위 문제는 가중치가 1로 동일한 경우에서의 최단 거리를 묻는 문제이므로 BFS를 돌리면 된다고 느낄 수 있다. 대표적인 유형의 문제인 걸로 느껴지는데, 지금 뇌가 정지한건지 도저히 내가 어디가 틀린지 모르겠다... 일단 내 풀이는 맞을 가망이 없었고, 아무리 봐도 모르겠어서 일단은 답안을 이해한 뒤에 내 방식대로 고쳐서 작성해 보았다. 내 풀이(틀린 풀이) 나는 인간이 있는 좌표로부터 최단거리에 있는 대피소를 BFS로 찾고, 그 최단 거리를 ans라는 정답 배열의 인간 좌표에 입력해주는 방식으..

문제 해석 이 문제는 돌을 골라내는 조합 로직 + 탐색 로직이 필요하므로 백트래킹 + BFS로 풀 수 있겠다 판단하였다. 결론적으로, 해석까지는 좋았는데, 로직의 구현 단계에서 디테일이 부족하여 틀리고 말았다. 문제 풀이 package 코드트리.그래프.BFS; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class 돌_잘_치우기 { private static int n, m, k; private static int[][] arr; private static int ans; private static List sPos = new Array..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이 문제 또한 최단 경로를 묻는 문제이므로 BFS로 접근하면 된다. 풀이 자바는 0으로 배열이 기본 초기화되니, 처음에는 0이면 이동이 불가한 것이라고 생각했다. public class 나이트 { private static int n; private static int[] dx = new int[]{-2, -1, 1, 2, 2, 1, -1, -2}; private static int[] dy = new int[]{-1, -2, -2, -1, 1, 2, 2, 1}; private static int x1,..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 최단 기간의 경로를 구하고 있으므로 BFS가 적절한 선택일 것이다. public class B2178 { static int[] dx = {0, 1, 0, -1}; static int[] dy = {1, 0, -1, 0}; static boolean [][] visited; static int[][] arr; static int n, m; public static void main(String[] args) throws IOException { BufferedReader br = new Buf..