https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 다익스트라 알고리즘을 응용하는 문제로 기본적인 정형화된 문제라기 보다는 생각을 깊이 해야 하는 문제이다. 예를 들어 1 번이 시작이고 5번(도착지라 가정)까지 COST 가 10 이하인 비용으로 최소 거리를 찾아야 한다고 가정해보자. 맨 처음으로 1 노드를 기준으로 인접한 노드의 COST 와 DISTANCE 를 탐색해준다. 또한 행렬표를 만들어서 특정 노드에서 ..
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 대표적인 다익스트라 알고리즘을 사용하는 문제이다. 행렬의 출발지점으로 부터 시작해서 마지막 지점까지 최대한 적은 비용으로 자취를 구하여 해당 총 비용을 구해주면 된다. 아래와 같은 행렬이 있고 링크가 (0,0) 지점 부터 (2,2) 지점까지 상하좌우로 움직이는데 가장 적은 비용을 지불하면서 도착하는 경로를 구해주면 된다. 여러가지 경로 중 아래의 경로가 존재할 것이다. 링크가 위..
https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1 1(1) -> 2(3) -> 4 총 5의 친밀도 점수로 위의 친밀도 점수 7보다 낮은 수치가 된다. 즉, 다익스트라 알고리즘을 사용하여 최소비용을 가지는 경로를 구하면 되는 문제이다. 1.JAVA 를 통한 풀이 import java.io.*; import java.util.*; public class Main { static ArrayList map; static int[] answer; static int[] prev; static int T,N,M; static int INF = Integer.MAX_VALUE; static int CASE = 1; ..
https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 각 격자모양 안에 토마토가 들어있는데, 토마토가 익은 경우 즉 값이 1인 경우에는 하루마다 주위의 토마토를 모두 익게 만든다. 또한 -1은 토마토가 없는 상태이다. 각 층의 상자안에 들어있는 토마토가 모두 익을때까지 소요되는 일수를구하는 문제로 해당 문제는 bfs(Breadth-First Search) 알고리즘을 사용하여 푸는 문제이다. 기존 토마토 문제는 높이를 고려하지 ..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 각 격자모양 안에 토마토가 들어있는데, 토마토가 익은 경우 즉 값이 1인 경우에는 하루마다 주위의 토마토를 모두익게 만든다. 또한 -1은 토마토가 없는 상태이다. 상자내의 토마토가 모두 익을때까지 소요되는 일수를 구하는 문제로 해당 문제는 BFS(Breadth-First Search) 알고리즘을 사용하여 푸는 문제이다. 해당문제를 해결하는 알고리즘은 아래와 같다. 1. 미로의 ma..
https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 이번 문제도 벽 부수기 문제의 일종으로 벽을 주어진 횟수만큼 부순다. 단, 낮과 밤이 존재해서 낮에는 벽을 부술 수 있지만, 밤에는 벽을 부술 수 없다. 칸을 이동할때마다 낮과 밤이 순서대로 바뀌고, 만약 이동하지 않은경우에는 머물더라도 낮과 밤이 바뀌게 된다. 해당 문제를 푸는 알고리즘은 아래와 같다. 1. 미로의 map (행렬)을 만들어 탐색준비 2. 미로와..
https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 이번문제는 벽 부수기 문제의 응용버전으로 이번에는 벽을 주어진 횟수만큼 부수고 이동할 경우에 미로탐색을 하여 최단거리를 구해주는 문제이다. 이번 문제도 기본적으로는 BFS(Breadth-First Search) 를 사용하여 해결할 수 있다. 이번에는 미로탐색1 문제에서의 로직을 사용해도 되지만 조금 변형해서 사용해보자. 1. 미로의 map (행렬)을 만들어 탐색..
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이번문제는 BFS(Breadth-First Search) 를 사용하여 해결하는 미로탐색 알고리즘의 응용 문제이다. 일단 위의 문제를 푸는 로직은 아래와 같다. 1. 미로의 map (행렬)을 만들어 탐색을 수행한다. 2. 미로와 같은 행렬의 크기인 새로운 행렬 visit(방문확인 행렬) 을 생성한다. 단, 해당 방문행렬의 요소들은 처음부터 모두 정수의 최대값으로 초기화 시켜..
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 알고리즘 분석 해당 문제는 재귀함수(recursive function)를 사용하는 대표적인 문제이다. 예를 들어 아래와 같은 5x5 matrix 가 주어졌다고 해보자. 아래에서 화살표 표시가 된 곳이 로봇청소기가 처음으로 위치하는 자리가 된다. 그리고 초기에 청소기가 바라보는 방향은 북쪽이라고 가정하자. (빈칸을 0 벽을 1 청소가 된 칸을 2로 가정하자.) 첫 번째로 로봇은 현재위치를 청소할 ..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 해당 문제는 DFS(Depth-First Search)와 BFS(Breadth-First Search) 알고리즘을 한번에 사용하는 대표적인 문제이다. 해당 문제를 풀기에 앞서 어떤식으로 풀어야할지 계획을 자보자. 1. 벽을 3개 세워줘야함. 2. 벽이 세워진 상태에서 바이러스를 퍼뜨려야함 3. 바이러스가 다 퍼진 map 에서 안전영역을 구해야함. 4. 각 경우마다 안전영역이 최대일때 개수를 출력. 1. 벽을 ..
