본문 바로가기
  • 주니어 개발자의
    RESTful 성장기

BFS3

[찾아라 프로그래밍 마에스터 - 게임 맵 최단거리] 문제 https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 분석 및 해결 정말 대표적인 BFS, DFS 그래프 탐색 문제였습니다. 하지만 최단 거리를 구할 때는 BFS가 짱짱맨이므로 BFS를 이용했다 import java.util.*; class Solution { public static int[] dy = {-1, 1, 0, 0}; public static .. 2021. 7. 26.
[21278 호석이 두 마리 치킨] 문제 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 접근 및 해결 1. 각 정점에 대해서 나머지 정점들까지의 최소 거리를 구한다. (플로이드-워샬) 2. 최대 100개의 정점이므로 3중 for문을 사용해 각 정점(집)에서 선택된 치킨 집 2개와의 최소 거리를 구한다. 3. 2에서 최소 값을 구하면 정답! #include #define INF 987654321; using namespace std; int N, M.. 2021. 6. 23.
[1446 지름길] 문제 - www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 분석 및 해결 단순한 bfs 문제였다. 지름길이 항상 |지름길 도착 위치 - 지름길 시작 위치| 보다 짧은 것은 아니라는 점을 주의해야 한다. 따라서, bfs를 통해 지름길을 이용하는 경우, 이용하지 않는 경우 모두에 대해서 탐색을 시도했다. 각 위치마다 모두 지름길을 가지고 있을 수도 있지만, 그렇지 않은 경우가 더 많을 거 같아 Map을 사용해서 graph를 구현했다. 소스 코드 impo.. 2021. 4. 15.

티스토리툴바