BFS
-
백준 5014번 스타트링크 :: 마이구미알고리즘 풀이/그래프 2017. 7. 23. 17:29
이번 글은 백준 알고리즘 문제 5014번 "스타트링크" 를 다뤄본다. 이전 글에서 다룬 1697번 숨바꼭질과 흡사하다. 조금 더 자세한 내용은 1697번 풀이를 보길 바란다. 1697번 풀이DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.보통 엘리베이..
-
백준 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의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇..
-
플로이드 와샬 알고리즘 :: 마이구미알고리즘 2017. 1. 27. 22:36
이번 글은 플로이드 와샬 알고리즘에 대해 다뤄본다.동적계획법을 기반으로 구현되는 알고리즘이다.위키백과의 정의를 보자. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다. 정의를 보다시피 최단 경로를 찾기에 좋은 알고리즘이다.시간복잡도는 3개의 반복문을 통해 O(n^3) 이다. 플로이드 알고리즘은 3개의 반복문이면 구현된다.코드를 보면 굉장히 짧고 간단하다. for (int k = 0; k <..
-
백준 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개가 되는 것이다.즉 제거되는 노드의 자식들을 함께 제거한다. 문제는 생각보다 간단하다.결국 제거되는 노드와 연결되어있는 자식들을 제거하면 된다.다른 사람들은 쉽게 배열만으로 풀었지만, 본인은 머리가 잘 안돌아갔다. 본..
-
[그래프] DFS와 BFS 구현하기 :: 마이구미알고리즘 2017. 1. 19. 22:15
이번 글은 자료구조 중 그래프를 다뤄본다.백준 알고리즘 1260번을 통해 진행하니 참고하길바란다. 그래프는 정점과 간선으로 이루어진 자료구조의 일종이다. G = (V, E) 그림을 보다시피, 정점과 간선이 무엇을 나타내는 지 알 수 있다.정점은 각 출발점 도착점과 같은 점이라고 보면 되고, 간선은 그 정점간 연결된 관계를 뜻한다. 무방향 그래프와 방향 그래프가 있다.말그대로 방향이 있는 그래프는 2->1로만 갈 수 있고, 무방향이라면 2->1, 1->2 가능하다는 것이다.여기서는 무방향 그래프를 기준으로 다뤄볼 것이다. 그래프의 탐색에 있어 DFS, BFS 방식이 있다.깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 2가지 방식을 알아보자.두 탐색은 모든 정점을 한번만 방문한다는 같은 목표를 가지고 ..