다익스트라 (20) 썸네일형 리스트형 [백준 / BOJ] 2917 늑대 사냥꾼 문제 출처 : www.acmicpc.net/problem/2917 2917번: 늑대 사냥꾼 첫째 줄에 N과 M (1 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개 줄에는 숲의 지도가 주어진다. 지도에 'V'와 'J'는 딱 하나만 있고, 적어도 하나의 '+'가 있다. www.acmicpc.net 늑대 현우는 사냥꾼을 피해서 최대한 안전한 경로로 집으로 도착해야한다. 사냥꾼은 나무뒤에 숨어있다. N*M 배열이 주어지고, 나무의 위치는 +, 현우의 위치는 V, 오두막의 위치는 J로 주어진다. 현우의 위치에서 집까지 가는 가장 안전한 경로에서 나무와 현우의 거리의 최솟값을 출력하는 문제다. 풀이 BFS를 돌려서 나무와 모든정점들에 최단거리를 저장해주고, 현우의 위치를 기준으로 다익을 돌려 가장 안전한 .. [백준 / BOJ] 17835 면접보는 승범이네 문제 출처 : www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net N개의 도시와 도시에따른 M개의 길, K개의 면접장이 주어진다. 승범이네라는 회사에서 신입사원을 뽑을려한다. N개의 도시에 살고있는 면접 준비자들은 자신의 도시에서 가장 가까운 면접장으로 가야한다. 이때 면접장 까지의 거리가 가장 먼 도시와 그때의 거리를 출력하는 문제다. (만약 거리가 가장 먼 도시가 여러군데라면 번호가 작은 도시를 출력하면.. [백준 / BOJ] 1261 알고스팟 문제 출처 : www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net N*M크기의 미로가 주어진다. 미로는 0,1로 주어지며 0은 빈 방 1은 벽이다. 알고스팟 운영진이 (1,1)에서 (N,M)으로 이동할때까지 총 몇개의 벽을 부숴야하는지 구하는 문제이다. 풀이 다익스트라를 이용해서 푸는문제다. 벽을 부순 횟수를 저장하는 배열을 만들고 배열의 모든칸을 최댓값으로 초기화 시켜준다. (나는 1000000000로 초기화 해줬음) 위 배열에는 해당 (.. [백준 / BOJ] 6118 숨바꼭질 문제 출처 : www.acmicpc.net/problem/6118 6118번: 숨바꼭질 문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 이전 1 2 3 다음