전체 글 (168) 썸네일형 리스트형 백준 4991 로봇 청소기 https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net bfs와 dfs를 결합한 문제... 처음에 Input 때문에 아주 고생했다. 로봇청소기가 있는 위치는 소문자 o 이다. 벽은 소문자 x이다. 처음에 이걸 안했다가 아주 애먹었다. 가장 가까운 방법만 골라서 가는 그리디 알고리즘은 얼핏 생각하면 최적일 것 같지만 최적이 아닐 수 있다. 증명이 안된다. 그러므로 사용할 수 없다. 이 문제의 Input의 크기가 몹시 작기 때문에 모든 경우의 수를 무작정 계산하는.. 백준 1507 궁금한 민호 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 플로이드 워셜을 응용한 문제다. 어렵지않다! 대신 문제 설명이 좀 이상하다. 분명 최소 거리쌍을 주었다고 했는데... -1이 나오는 케이스는 '현재 주어진 거리쌍이 최소 거리쌍이 아닌 경우'다. 문제가 좀 이상하지 않은가 싶긴한데... 암튼 그렇다. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import jav.. 백준 9370 미확인 도착지 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 다익스트라 문제인데 변형이 있다. 다익스트라 알고리즘은 분명 한 점(시작점)에서 다른 모든 점까지의 최단 거리를 구할 수 있는 알고리즘이다. 하지만 그 최단 거리의 경로 자체는 유일하지 않을 수도 있다. 그걸 잘 지적한 문제라고 생각한다. import java.awt.image.AreaAveragingScaleFilter; import java.io.*; import java.util.*; .. 이전 1 ··· 23 24 25 26 27 28 29 ··· 56 다음