거울의 반사되는 조건과 기존에 자주 풀던 최단 경로가 아닌 도달할 수 있을 때 '거울의 최소 수'를 구하는 문제라서 더욱 어렵게 느껴졌다.문제를 읽고 구현을 BFS로 할지, DFS로 할지 고민했는데 BFS로 하게될 경우 거울의 개수를 어떻게 관리하고, 그에 따른 visited 배열을 관리하는 것이 어려울 것 같아서 바로 DFS로 노선을 틀었다. 최소 거울의 개수를 구하면 되니깐 거울을 1개 이용했을 때 반대편 문제 도달하는지 확인하고, 도달 못하는 경우 거울의 수를 늘려서 다시 2개, 3개,, N개가 될 때까지 DFS를 반복했다. 그러니 당연하게도 시간초과가 났다.  이 문제는 BFS로 풀어야되는 문제였다. 다른 사람의 BFS 풀이를 보면서 내가 잘못 접근한 부분을 찾아봤다. 1. 거울의 개수를 어떻게 ..

1. 문제  2. 풀이 방법문제를 이해하기 위해 예제로 주어진 트리를 그려봤다. 루트가 주어지기에 자연스럽게 계층 구조가 형성된다. 서브트리의 개수는 곧 자기와 자식들의 정점 수를 모두 합친 수였다. 시간복잡도를 따져봤을 때 정점의 개수는 십만이고, 쿼리의 개수도 십만이기에 O(N)이나 O(logN)으로 풀어야할 것 같았다.어떻게하면 한 번의 쿼리 때 logN의 시간복잡도를 가질 수 있을까 고민해보다가 그냥 한 번 전체탐색을 돌려서 모든 정점의 서브트리의 개수를 구한 후 쿼리에 맞춰 답을 출력해주면 될 것 같았다. 서브트리를 구하는 방법은 재귀적으로 자식 노드들을 방문하면서 개수를 구하면 될 것 같아서 바로 코드로 옮겨봤다.우선 트리를 형성하기 위해 ArrayList 배열을 이용하였다. 아래와 같이 주어..

1. 문제 2. 어떻게 풀까?MST의 비용을 구할 수 있어야 풀 수 있는 문제로 진행되는 라운드 동안 하나씩 가중치가 낮은 간선을 제거하면서 MST의 비용을 구하는 문제이다. 잊고 있던 MST 비용 구하는 개념을 다시 복습해보자Edge 간선을 우선순위 큐에 모두 삽입한다 가중치가 낮은(또는 높은)순으로 우선순위 큐에서 빼낸다Edge를 이루는 두 정점을 이을 시 싸이클이 형성되는지 확인한다 (find 연산)싸이클이 형성되지 않으면 해당 Edge를 MST를 이루는 간선으로 추가한다.간선의 개수가 N-1개가 되면 비용을 리턴한다. N-1개가 되지 못하면 MST 그래프를 만들 수 없다 먼저 MST를 구하는 코드를 짠다.public static int MST(int k, PriorityQueue pq){ i..

문제 링크 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 분류 브루트포스 알고리즘, 플로이드–워셜, 그래프 이론, 그래프 탐색, 최단 경로 문제 설명 컴공 출신은 치킨집을 하게 되어있다. 현실을 부정하지 말고 받아들이면 마음이 편하다. 결국 호석이도 2050년에는 치킨집을 하고 있다. 치킨집 이름은 "호석이 두마리 치킨"이다. 이번에 키친 도시로 분점을 확보하게 된 호석이 두마리 치킨은 도시 안에 2개의 매장을 지으려고 한다. 도시는 N 개의 건물과 M 개의 도로로 이루어져 있다..

1. 문제 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 문제 설명 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈..