'알고리즘'에 해당되는 글 2건

  1. 2012.07.08 [UVa 10034] Freckles
  2. 2012.06.17 [UVa 10187] From Dusk Till Dawn (2)

[UVa 10034] Freckles

2012. 7. 8. 17:45 from 알고리즘


이번주 스터디에서 풀었던 문제. 3주 전 황혼에서 새벽까지에 이어서 이번에도 그래프 문제를 선택했다. 지난번 문제는 (응용이 좀 있긴 하지만) DAG에서의 최단경로를 찾는 문제였고 이 문제는 가중치가 있는 그래프의 MST(Minimmum Spanning Tree)를 찾는 문제다.

Minimmum Spanning Tree

어떤 그래프 G=(V,E)가 있을 때, V의 모든 정점을 연결하는 트리를 이루는 E의 부분집합인 모서리들을 신장 트리(spanning tree)라고 부른다. 모서리에 가중치가 있는 그래프에서 최소 신장트리를 찾아야 하는 경우가 많이 있는데, 최소 신장 트리란 모서리의 가중치의 합이 최소가 되는 트리를 말한다.

최소 신장 트리를 구할 때는 주로 크루스칼 알고리즘(Kruskal’s algorithm)이나 프림 알고리즘(Prim’s algorithm)을 사용한다. 이 두 알고리즘은 거의 모든 알고리즘 수업에서 다룬다. 프림 알고리즘은 프로그래밍하기도 쉽고, 약간만 바꾸면 다익스트라(Dijkstra)의 최단 경로 알고리즘을 만들 수 있다.

Prim’s algorithm

이번에 알고리즘 공부하면서 10년 전에 처박아둔 대학교 알고리즘 강의 자료를 들춰봤는데, 나도 그 때 크루스칼과 프림 알고리즘을 모두 배웠더군…;; 난 처음 보는 알고리즘인 듯 했는데 헐… 근데 다시 읽어보니 예전에 배웠던 게 기억이 났음ㅎ

프림 알고리즘은 어떤 정점에서 시작해서 단계별로 최소 신장 트리를 키운다. 각 단계에서 신장 트리에 정점을 하나씩 추가한다. 모든 가능한 방법을 시도하는 알고리즘을 써서 올바른 최소 신장 트리를 만들 수 있다. 트리에 있는 정점과 트리 밖에 있는 정점을 연결하는 모서리 중에서 가장 가중치가 작은 것을 추가하면 된다. 게임에서는 단순히 MST를 찾는 것 보다는 최단 경로 탐색에 쓰이는 다익스트라 알고리즘이 보다 유용할 텐데, 다음엔 이런 문제를 한 번 풀어봐야겠다.

주근깨 – Freckles

문제에서는 주근깨라는 메타포를 연결해 두었지만, 자세히 분석해보면 사실 주어진 가중치 그래프에서 MST를 구해내는 것 이외에 다른 변형은 아무것도 없는 가벼운 수준의 문제다. 가볍다는 기준은 그래프 알고리즘 이론들을 머리에 정리해두고 있다는 전제에서겠지만.. 아무튼 프림 알고리즘을 착실히 적용하면 금방 풀 수 있음.

제출 코드

n073.cpp


'알고리즘' 카테고리의 다른 글

[UVa 10034] Freckles  (0) 2012.07.08
[UVa 10187] From Dusk Till Dawn  (2) 2012.06.17
Posted by leafbird 트랙백 0 : 댓글 0

댓글을 달아 주세요

방향이 있는 그래프(directed graph)의 너비 우선 탐색(BFS;Breadth First Search)을 이용하는 문제다. 대학교 알고리즘 수업 시간에 만져본 뒤로 실무에서 그래프는 한 번도 만져본 적이 없는 것 같다.

 

그래프의 탐색 : BFS / DFS

복습의 차원으로 그래프의 탐색을 정리해보자. 임의의 시작점으로부터 출발하여 그래프 내의 정점과 모서리를 중복 없이 한 번씩 방문하는 것을 탐색이라고 하며, 방문 순서에 따라 크게 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)으로 분류할 수 있다.

BFS는 시작점부터 연결된 모서리를 통해 탐색해 나가면서 발견된 정점들을 순서대로 처리하는 방식이다. 정점들은 출발점과 동일한 거리(=출발점부터 해당 정점까지 연결된 모서리의 수)에 놓인 순서대로 처리된다. 그렇기 때문에 bfs에서 발견된 정점까지의 경로는 시작점으로부터의 최단경로로 방문하게 되어, 가중치 없는 그래프인 경우라면 존재하는 정점들을 모두 순회하지 않더라도 최단경로를 찾을 수 있는 탐색 방법이다. 가중치 있는 그래프에서 최단경로를 찾기 위해서는 다익스트라 알고리즘을 이용해야 한다.

DFS는 백트래킹과 똑같은 개념으로 그래프를 탐색한다. 방문 가능한 정점이 존재하지 않을 때까지 검색해서 들어갔다가 더이상 진행 불가능하면 다시 되돌아오는 방식이다. dfs 구현을 위해 stack 자료구조가 필요하지만, 보통은 재귀호출을 통해 구현하기 때문에 호출과정에서 자동으로 stack이 만들어지게 된다.

 

황혼에서 새벽까지 – From Dusk Till Dawn

이번 스터디 교재 알고리즘 트레이닝 북의 문제들 난이도가 대체적으로 상당한 편이다. 어느 문제를 고를까 하다가 문제 읽고 이해해서 비교하는 것만으로도 상당한 시간 소요가 예상되어, 그냥 제목이 제일 근사한 문제를 골랐다. (…) 그런데 문제에 관련한 정보를 얻으려고 구글링을 했더니 죄다 영화에 대한 이야기만 나와서 안 좋더라...;;

문제는 18:00부터 06:00까지만 움직일 수 있는 뱀파이어가, 출발역부터 도착역까지 주어진 노선을 이용해 움직이면서 몇일의 기간을 소요해야 하는가를 구하는 문제이다. 얼핏 보면 가중치가 없는 방향성 그래프의 최단거리 찾기 문제로 보이지만, 이용하는 열차의 수를 최소로 하는 것이 아니라 소요 기간을 최단으로 찾아야 하므로 응용이 필요하다.

문제 풀이를 위한 과정을 순서대로 간단히 정리해보면

  1. 입력으로 들어오는 노선 중, 뱀파이어가 이용할 수 없는 06:00 ~ 18:00 시간 동안에 출발하거나 이동중인 노선은 모두 무시하고 그래프를 구성한다.
  2. 그래프의 정점이 되는 정차역들마다, 출발역으로 부터 소요되는 기간을 날짜와 도착시각으로 나누어 기억한다. 소요 날짜의 초기값을 충분히 큰 값으로 설정해두고 검색을 시작한다.
  3. BFS 방식으로 탐색을 시작한다. 탐색에서 발견된 정차역에는 현재까지 계산된 가장 짧은 방문 소요시간이 저장되어 있다. 역에 연결된 각각의 노선을 이용해 도달하는 소요시간이 도착역에 저장된 소요시간보다 짧다면 이를 갱신해주고 FBS queue에 큐잉한다.
  4. [중요]한 번 방문한 정차역을 다음 탐색에서 무조건 제외하는 것이 아니라, 기존에 발견된 루트보다 더 짧은 소요시간의 경로가 있다면 해당 정차역을 다시 탐색 대상으로 처리한다.
  5. 탐색 도중 도착역을 만나게 되더라도, 탐색을 중단하지 않는다. 과정 4에서 설명한 것처럼 더 짧은 경로를 발견하면 값이 갱신될 수 있기 때문이다.

이렇게 하면 ideal한 BFS처럼 모든 정점을 딱 한번만 방문하는 것은 아니지만, 그렇다고 백트래킹으로 존재 가능한 모든 루트를 탐색해 보는 것도 아닌 애매한 처리성능(…)의 솔루션을 얻을 수 있다.

 

주의사항 : 디버깅 하기가 어렵습니다.

문제를 해결하는데 시간이 많이 걸렸다. 그래프 탐색 코드를 작성하는 것이 하도 오랜만이라 시간을 쓴 것도 있지만, 그것보다 이 문제 디버깅을 하기가 쉽지가 않다. 책이나 온라인 사이트에 제시된 입력 데이터만 가지고는 성공적으로 문제를 풀었는지 확인하기가 힘들다. 그래서 채점을 해보면 틀린 답이라고 나오는데 어디가 왜 틀렸는지를 알 수가 없는 것이 너무 답답했다. 혼자 힘으로 풀 수 있는 데까지는 최대한 풀어보려고 했는데… 뭐가 문제인지를 알 수가 없으니 내가 지금 문제를 잘못 이해하고 있나 하고 장님이 코끼리 다리 만지듯 코드를 디버깅… 애매하게 시간만 잡아먹고 있으니 너무 속이 상했다. 그나마 UVa 사이트에 연결된 게시판에서 같은 문제로 고민하는 다른 프로그래머들의 글들을 찾아 읽고 겨우 실마리를 찾아서 해결. UVa Online Judgewww.programming-challenges.com는 틀렸으면 틀렸다고만 하지 말고 어떤 입력에 어떤 잘못된 답이 나왔는지도 알려주면 좋겠다. 아마 고정된 데이터가 공개되면 어뷰징을 가려내기가 힘들테니 데이터를 숨기는 것 같은데… 하여튼 이번에 너무 애먹었다구 ㅠㅠ

 

제출 코드

n071.cpp


ps : 채점시 입력되는 열차 출발시각은 24 보다 클 수 있더군요… (뭐이자식아!?)



'알고리즘' 카테고리의 다른 글

[UVa 10034] Freckles  (0) 2012.07.08
[UVa 10187] From Dusk Till Dawn  (2) 2012.06.17
Posted by leafbird 트랙백 0 : 댓글 2

댓글을 달아 주세요

  1. addr | edit/del | reply 컴공백수 2013.08.01 05:46

    열차 출발시각이 24 보다 클 수 있다니... 이문제를 풀다가 막혔었는데, 이 부분을 수정하니까 accepted를 받았네요ㅎㅎ 좋은정보 감사합니다~