백준/그래프 (22) 썸네일형 리스트형 [KOI] 백준 2638 - 치즈 www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net KOI 중등부 치즈문제이다. 중등 치즈에서는 치즈 격자가 외부 공기와 두변 이상 접촉해야 녹는다고 하며 치즈를 모두 녹이는데 필요한 시간을 구해야 한다. 또한 모눈 종이에 가장자리에는 치즈가 놓이지 않는다는 조건이 있다. 이를 공기의 관점으로 접근하면 문제를 해결할 수 있다. 1. BFS로 공기를 흘려보낸다. 가장자리에는 치즈가 놓이지 않으므로 탐색 시작점은 (0, 0)이 적절할 것이다. 공간을 탐색하.. 백준 - 1219 : 오민식의 고민 https://www.acmicpc.net/problem/1219 문제의 맥락을 보면 최단 경로 알고리즘을 사용해야 되는 것으로 보인다. 출력 문단을 살펴보면 3가지 케이스를 구분할 것이 요구됨을 알 수 있다. 도착이 가능할 경우 소지금의 최댓값 도달 자체가 불가능할 경우 "gg" 출력 도착했을 때 돈이 무한으로 발산한다면 "Gee" 출력 이 케이스들을 개별적으로 생각해보자. 첫 번째는 이익이 최대로 되는 경로를 찾으면 된다. 두 번째는 도달 가능성을 판단하면 된다. 세 번째가 생각하기 어려울 수 있는데, 경로를 탐색하던 중 음수 사이클(문제에서는 이익 사이클)로 진입했지만 도달할 수 있는 경로가 존재한다면 돈을 무한정 벌게 되는 것이므로 사이클 존재 여부와 도달 가능성을 판단하면 된다. 즉 세가지를 종.. 이전 1 2 3 4 5 다음
