BOJ 문제 풀이

백준 [BOJ] 10217 : KCM travel

10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 조건이 있는 최단거리를 찾는 문제. 한 도시에서 다른 도시로 가는 최단 거리를 찾는 것이므로 이런 경우에는 다익스트라 알고리즘을 쓰는게 좋다고 알려져있다. 단순 dfs / bfs 를 사용하는 경우는 가중치가 모두 같은 경우이다. 방문했던 곳에서는 다시 탐색을 진행하지 않는 특성 탓이다. 시작점 ~ 방문해야 할 지점까지의 거리를 s라고 하자. 만약 가중치가 다른 상황에서 이미 방문했던 곳을 재방문했다고 해보자 재방문 했을 때 기..

백준[BOJ] 1707번 : 이분그래프 - BFS, DFS

1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net BFS, DFS를 연습하기 좋은 문제라는 생각이 든다. 처음에 이분 그래프의 개념을 아예 몰라서, 이진트리를 의미하는 줄 알고 한참 고생했다.... 그림으로 보면 이해가 빠르다. 아래와 같다. 인접한 정점을 다른 색으로 모두 칠할 수 있으면 이분 그래프이다. 이분 그래프의 특징 인접한 정점들을 다른 색을 구분할 수 있다. 순환할 수 있다.(2가지 색으로 구분 가능하면 된다.) 최대 이분 매칭 문제(Maximum Bipartite Matching Pr..

백준[BOJ] 1520번 : 내리막길

1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 처음 문제의 이미지를 보자마자 깊이우선탐색/넓이우선탐색 문제일것이라는 생각이 들었다. 경로의 개수를 찾아야하는 이 문제에서는 DFS가 적합하다는 직감이 느껴졌다. 이 문제에서는 여러 종류의 경로가 서로 중첩되는 경우를 반드시 고려해야한다. 만약 BFS로 탐색을 진행하게 되면 가능한 모든 경로를, 같은 깊이로, 탐색을 진행한다. 이 때에는 (다른 깊이, 같은 지점)에서 만났을 경우를 처리하는 게 복잡하다고 생각된다. 이 글 쓰고 나서 시도해봐야겠다. DFS로 가능한 하..