문제 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 방법 어느 섬에서 다른 섬에 도달했을 때의 최소 거리를 구해야하는 문제다. N = 100이하이기 때문에 막연하게 생각해봤을 때 O(N^3)이여도 문제가 없을 것 같아 고안해낸 풀이는 다음과 같다. 떨어져 있는 섬끼리 구분하기 위해서, 각 섬에 그래프 탐색을 이용해서 번호를 붙인다. 번호 붙인 섬마다 BFS로 퍼져나가면서 탐색 탐색 중 다른 섬을 만났을 때 거리를 비교해보고 최소일 경우 ans..
분류 전체보기
문제 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 풀이 방법 2차원 공간을 탐색하면서 문서 몇 개를 훔칠 수 있을까를 계산하는 문제다. 이 문제만의 특이한 점은 다음과 같다. 처음 시작점이 정해져 있지 않고 주어진 2차원 공간 밖 아무데서나 시작할 수 있다. 열쇠를 얻으면 그에 알맞는 문을 열고 지나갈 수 있다. 열쇠는 알파벳 a~z까지 있으므로 총 26개다. 첫 번째는 주어진 2차원 공간 밖의 테두리를 빈 공간으로 만들어준다. 크기를 h+2, w+2로..
최단 경로 찾기 알고리즘 최단 경로 찾기 알고리즘에는 여러가지 알고리즘들이 있는데, 상황에 따라 다르게 사용할 수 있다. 게임이 어떤 케이스인지 생각해보고 적용하면 된다. 한 개의 시작노드와 한 개의 도착노드 Greedy Best First Search - 휴리스틱 값에 기반한 우선순위 큐 사용. 즉 f(x) = h(x) A* - 게임에 주로 사용된다. 아래 설명 참고 한 개의 시작노드와 여러 개의 도착노드, 또는 여러 개의 시작노드와 한 개의 도착노드 Breadth First Search(BFS) - 가중치 없는 간선 Dijkstra(다익스트라) - 음수가 아닌 가중치가 있는 간선 Bellman-Ford(벨만포드) - 양수 또는 음수 가중치가 있는 간선 여러 개의 시작노드와 여러 개의 도착노드 Floy..
문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 방법 벽을 부쉈을 때 이동할 수 있는 칸의 갯수를 구하면 되는 문제다. 단, 모든 벽마다 탐색을 해서 이동할 수 있는 칸 개수를 구하면 시간 초과가 발생한다. 예를 들어 다음과 같은 케이스가 들어온다고 해보자. 예시: 6 6 101010 000000 101010 000000 101010 000000 1에서 탐색을 시작할때마다 모든 0의 개수를 반복적으로 구하기 때문..
