본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )/벨만포드,다익스트라,MST

 (27)
[백준 / 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
[백준 / BOJ] 11657 타임머신 (벨만포드) 문제 출처 : www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net N개의 도시가 있다. 1번도시에서 출발하여 모든 도시로 갈때, 최소한의 시간으로 가는 경우를 구한다. 도시간의 시간에는 음수가 존재할수있으며, 이는 타임머신을 타고 과거로 가는경우이다. 만약 과거로 계속해서 갈수있으면 -1 을 출력하고 종료한다. 1번도시에서 해당하는 i번 도시로 갈수없다면 -1을 출력한다. 풀이 음수가중치가 존재함으로,..

티스토리툴바