알고리즘 풀이/그래프
-
백준 1697번 숨바꼭질 :: 마이구미알고리즘 풀이/그래프 2017. 7. 23. 17:15
이번 글은 백준 알고리즘 문제 1697번 "숨바꼭질" 을 다뤄본다.문제 접근 방법은 BFS를 통해 해결했다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇..
-
백준 1987번 알파벳 :: 마이구미알고리즘 풀이/그래프 2017. 7. 22. 22:36
이번 글은 백준 알고리즘 문제 1987번 "알파벳" 을 다뤄본다.문제 풀이는 DFS를 응용하여 해결할 수 있다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있..
-
백준 2468번 안전 영역 [DFS] :: 마이구미알고리즘 풀이/그래프 2017. 6. 18. 22:48
이번 글은 백준 알고리즘 문제 2468번 "안전 영역" 을 다뤄본다.정올 초등부에서 출제된 문제이다.초등부이지만, 정답률은 30%인 것을 볼 수 있다.DFS, BFS - http://mygumi.tistory.com/102 문제 접근은 DFS 또는 BFS를 활용할 수 있다.기본적인으로 DFS 및 BFS 기본 지식을 가지고 있다면 충분히 풀 수 있다.여기서는 DFS를 통해 문제를 풀어보겠다. 위 그림은 높이가 4와 6의 경우를 나타내고 있다. 흰색 영역의 수를 찾는 문제가 된다.그래프에서는 이 영역을, 연결 요소의 개수라고 볼 수 있다.즉, DFS 탐색이 이루어지는 횟수 중 가장 큰 수가 정답이 된다. 높이를 1부터 100까지 경우 각각 DFS 탐색을 하면 된다. public static void dfs(..
-
백준 5567번 결혼식 [그래프] :: 마이구미알고리즘 풀이/그래프 2017. 4. 10. 14:21
이번 글은 백준 알고리즘 5567번 "결혼식" 을 다뤄본다.그래프를 통해 문제를 해결할 수 있다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오. 문제는 상근이의 친구와 상근이의 친구의 친구를 초대할 수 있다.상근이의 친구상근이의 친구의 친구위의 2가지의 조건에 ..
-
백준 1507번 궁금한 민호 [플로이드] :: 마이구미알고리즘 풀이/그래프 2017. 2. 3. 17:36
이번 글은 백준 알고리즘 문제 "궁금한 민호"를 다뤄본다.플로이드 와샬 알고리즘을 통해 해결한다.백준 알고리즘 1507번 궁금한 민호 - https://www.acmicpc.net/problem/1507 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.예를 들어, 예제의..
-
백준 2146번 다리 만들기 :: 마이구미알고리즘 풀이/그래프 2017. 1. 24. 22:52
이번 글은 백준 알고리즘 문제 2146번 "다리 만들기" 를 다뤄본다.이 문제는 BFS DFS 활용 문제이다.하단에 비슷한 문제들이 나열되어 있다.DFS, BFS 관련 글.http://mygumi.tistory.com/102 위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나,위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).지도가 주어질 때, 가장 짧은 다리 하..
-
백준 1068번 트리 :: 마이구미알고리즘 풀이/그래프 2017. 1. 24. 22:01
이번 글은 백준 알고리즘 1068번 문제 "트리" 를 다뤄본다.문제명 그대로 트리 문제이다.백준 알고리즘 1068번 트리https://www.acmicpc.net/problem/1068 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이 때, 1번을 제거한다고 하면, 다음과 같이 된다. 위 그림과 같이 1번을 제거한다면 리프노드는 2번 노드 하나밖에 남지 않는다.만약 3번을 제거한다면 2번, 4번 노드가 남아 2개의 리프노드가 남게 된다.그렇다면 0번이 제거된다면, 리프노드는 0개가 되는 것이다.즉 제거되는 노드의 자식들을 함께 제거한다. 문제는 생각보다 간단하다.결국 제거되는 노드와 연결되어있는 자식들을 제거하면 된다.다른 사람들은 쉽게 배열만으로 풀었지만, 본인은 머리가 잘 안돌아갔다. 본..
-
백준 9466번 텀 프로젝트 :: 마이구미알고리즘 풀이/그래프 2017. 1. 22. 17:31
이번 글은 백준 9466번 문제 "텀 프로젝트" 를 다뤄본다.백준 알고리즘 문제 9466번 텀 프로젝트 https://www.acmicpc.net/problem/9466DFS, BFS 관련 글.http://mygumi.tistory.com/102 예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.12345673137346위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라. 문제를 보면 10451번과 흡사하다.이 문제도 사이클을 찾으면 된다.10451번과 다른 점은 중복 입력이 주..