[Algorithm] 화이트 칼라 (Algospot – WHITECOLLAR)

By | 2018-08-09

출처

  • https://algospot.com/judge/problem/read/WHITECOLLAR

난이도

  • 하 – 중 – 상 – (최상) – 풀지 못함

문제

  • 도둑이 특정 도시에서 출발해서 목적지 도시까지 최대한 빠른 길로 도망갈 예정이다. 도둑을 잡기 위해서 도둑이 방문할 도시를 미리 찾는 문제이다. 결과적으로 도시(Node)와 도시 간을 연결하는 길(Edge: 일방통행)이 주어졌을 때 Shortest Path를 찾는 문제이다.

후기

  • 처음 문제를 읽고 Shortest Path를 찾는 문제로 생각했다. 그래서 단순히 Stack을 사용해서 Shortest Path 하나를 찾도록 코딩을 했다. 하지만, 문제에 숨겨진 의도를 제대로 파악하지 못하고 문제를 풀었다. 문제의 의도는 Shortest Path가 여러 개 있을 때는 모든 Short Path를 다 찾아야 하는 것이었다. 현재 나의 실력으로 최상 난이도 문제라고 생각한다. 이보다 어려운 문제는 풀지 못할 것 같다.
  • Shortest Path의 경우 동일한 도시를 2번 방문하는 경우가 없다. 그래서 Stack (First In First Out: FIFO)을 사용하여서 방문한 도시는 Stack에 추가하였다. 그리고 순서대로 Stack에서 Pop하여서 다음 방문 도시를 탐색하면 된다. 처음에는 단순히 Pop을 하고 한번 방문한 도시를 다시 방문하지 않기 때문에 동일한 도시를 방문하는 경우 계산을 하지 않았다. 하지만 그렇게 하면 동일한 길이를 가진 경로를 모두 계산하지 않게된다. 예를 들어 1 -> 2 -> 4 -> 5로 가는 방법과 1 -> 3 -> 4 -> 5로 가는 경로가 있으면 두개중 먼저 5번에 방문하는 경로만 검색을 하게 된다.
  • 여러개의 Path를 계산하기 위해서 같은 Path의 길이를 가진 길이 여러 개 있으면 방문 도시의 개수를 Merge 하는 부분이 필요하다. 위 예의 경우 4번 도시(Node)에 방문하는 2가지 경우를 하나로 Merge 하여 다음 계산을 수행하면 된다.
  • 처음에는 방문 도시를 확인하기 위해서 단순 Integer 리스트를 사용했다. 실행시간을 단축하고 싶어서 Bit 연산을 사용하여 Integer 리스트 크기를 최소화했다. 이 부분에서 대략 30ms 정도 시간이 단축되었다.
  • 결과적으로 같은 길이를 가진 여러 개의 Path를 계산해야 하므로 난이도 높았던 문제라고 생각한다. 특히, Algospot의 경우 몇 개의 오답이 발생했는지 등을 확인할 수 없어서 문제를 해결하는 데 더 어려움이 있는 것 같다. 개인적으로 코딩을 연습하는 관계로 Stack부터 모든 부분을 다 작성하였다. 하지만, 이미 잘 만들어진 std::vector 등을 사용하면 더 효율적으로 코딩을 할 수도 있는 것 같다. 아마 실행시간도 많이 단축될 것으로 생각된다.
  • 추가: White-Collar의 의미가 궁금해서 네이버에 검색을 해보았다. 화이트 칼라는 “정신적·지적 노동을 주체로 하는 근로자의 속칭으로 전문직·기술직·관리직·사무직 종사자”를 의미한다. 문제의 White-Collar 제목과 문제의 연관성을 잘 모르겠다.

코드

  • Stack을 사용하여 Shortest Path를 탐색하는 코드
  • 실행 시간: 96ms (제일 빠른 실행 시간 대비 30ms (3배 느림))

출처

  • https://terms.naver.com/entry.nhn?docId=473831&cid=42120&categoryId=42120

Leave a Reply

Your email address will not be published. Required fields are marked *