늦깎이 IT

[백준 1976번] 여행가자 URL 1. 전형적인 Union-Find 문제입니다.2. 각 여행지들의 부모노드를 저장하고, 모든 노드들의 부모노드가 같다면 어느 노드부터 시작하더라도 모든 노드들을 방문할 수 있기 때문에 YES, 하나의 노드라도 부모노드가 다르다면 NO를 출력합니다. [소스 코드] 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293import java.io.BufferedReader;import java.io.IOExceptio..

[백준 1717번] 집합의 표현 URL 기본적인 Union-Find 문제이므로 이전 포스팅 글을 참고하시기 바랍니다.2019/03/25 - [알고리즘 이론] - [알고리즘] 유니온 파인드 (Union-Find) :: 늦깎이 IT [소스 코드] 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayL..

이 포스팅은 [이곳] 에서 수정 및 보완되었습니다. 꼭! 참고하시기 바랍니다. 이 포스팅에서는 유니온 파인드의 연산 과정을 [그림] 위주로 이해하기만 하면 될 것 같습니다. 오늘은 '유니온 파인드 (Union-Find)' 알고리즘을 포스팅합니다. 유니온 파인드는 대표적인 그래프 알고리즘으로써 서로소 집합(Disjoint-Set) 알고리즘이라고도 불린다.여러 개의 노드가 존재할 때, 두 개의 노드를 선택해서 이 노드들이 서로 같은 그래프에 속하는지 판별하는알고리즘이다. 아래와 같은 노드들이 있다고 가정한다. 위 그림에서 노드 1, 2, 5와 3, 4, 6은 각각의 그룹으로 나뉘어있다. 위의 상태에서 5번 노드가 어느 그룹에 속해있는지 확인하는 것을 Find-Set이라고 한다. 임의의 노드들이 같은 그룹에 ..

[백준 2146번] 다리 만들기 URL 1. 각 섬마다 번호를 매긴다 (2, 3, 4, ....) 2. 그리고 모든 섬들을 큐에 넣어주고 BFS를 돌린다. BFS를 돌릴 때 다음 칸이 0이라는 뜻은 바다라는 뜻이므로해당 섬의 번호로 땅을 확장한다. 3. 다음 칸이 0도 아니고, 현재 위치의 땅 번호와도 다르다면, 다른 땅이 그곳까지 확장됐다는 뜻이므로 거리를 계산한다. 4. 거리를 계산하는 방법은 dist라는 2차원 배열을 따로 만들고 BFS 탐색을 할 때 땅이 한 칸 확장되었다면 거리또한 1씩 증가시키는 것이다. [소스 코드] 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354..

[백준 2573번] 빙산 URL 1. 빙산을 녹일 때 주의할 점이 있다. 왼쪽위부터 오른쪽아래까지 map을 탐색하면서 빙산을 녹일 때, 임의의 한 빙산을 녹일 때, 인접한 부분에 바다(0)가 있다고해서 무조건 녹이면 안되고, 바다로 된 자리가 현재 시점에 바다가 된건지 이전 시점에 바다가 된건지 확인해야한다. 2. melt() 메소드를 보면, 같은 시간내에 바다가된 경우 curMelt라는 boolean 배열에 체크를 해준다. 3. 빙산을 한 회 녹였다면, BFS탐색을 시작해서 빙산이 두 덩어리 이상이 되는지 확인한다. 4. BFS 탐색 후에, 빙산이 두 덩어리가 안되었다면 map을 전체탐색하며 빙산이 모두 녹았는지 확인한다.빙산이 모두 녹아버렸다면 0을 출력한다. [소스 코드] 12345678910111..

[백준 2468번] 안전 영역 URL 1. 비가 내리지 않을 경우, 안전지대는 1로 초기화한다. 2. 비는 안전지대의 최대 높이만큼만 내리면 된다. 최대 높이보다 비가 더 많이 내릴 경우는 어차피 안전지대는 0이되기 때문이다. 3. 비를 1씩 내릴때마다 Map의 값을 -1 해주며, BFS탐색을 하고 최대 값을 찾는다. [소스 코드] 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061..

[백준 9466번] 텀 프로젝트 URL 1. 사이클에 들어가지 못한 노드들의 갯수를 묻는 문제이다. 2. 우선 1번부터 N번까지의 노드들을 순차적으로 탐색한다. 3. 어느 노드부터 시작해서 방문하지 않았거나 그룹에 속하지 않았을 경우 계속해서 탐색을 진행한다. 4. 이미 방문했거나 그룹에 들어간 노드를 만나면 탐색을 멈추고, 그 노드의 번호를 기억한다. 5. 아래와 같은 입력이 주어졌을 때를 생각해보자.1부터 탐색을 시작해서, 3에서 탐색을 끝낸다. 탐색을 하며 각 노드들을 list에 저장한다.3에서 탐색이 끝나면 cur 에는 3이 저장되어 있다.list를 돌면서 처음 시작점과 끝나는 점을 비교한다.시작점 == 끝점(cur)을 찾았으면 그때의 list 인덱스를 저장하고 break문으로 for문을 빠져나온..

[알고스팟] 고대어사전 URL 1. 입력으로 주어지는 단어의 순서가 사전 순서로 배치되어 있다. 2. 각 단어들마다 비교를 통해 각 문자들간의 우선순위를 비교해주는 연산이 필요하다. 3. 예를 들어, acb와 abb가 입력되었을 경우 맨 앞자리 알파벳은 같으므로 패스하고 두 번째 자리인 c가 b보다우선한다는 것을 표시해야한다. 4. 각 단어들간의 우선순위는 26 X 26 인접행렬로 표현해도되고 연결리스트로 표현해도된다. 5. a~z 까지의 알파벳을 순차적으로 탐색하되 연결되어 있는 알파벳이 있다면 다시 그 알파벳부터 DFS탐색을시작한다. 6. 순서가 정해져있는 경우이므로, 위상정렬을 한다고 생각하면 된다. 1234567891011121314151617181920212223242526272829303132..